Práctica 4: Paralelización con OpenMP

Práctica 4: Programación paralela con OpenMP

Resumen

El objetivo de esta práctica es presentar OpenMP, un modelo de programación paralela en máquinas de memoria compartida. OpenMP permite explicitar las zonas de código paralelo mediante directivas de compilación. Tras describir el entorno de trabajo, se realizará un estudio teórico y práctico que presenta y ejercita el modelo de ejecución de OpenMP y sus directivas básicas. Finalmente se plantean códigos en los que debe analizarse la viabilidad de su ejecución en paralelo y en su caso paralelizar mediante directivas OpenMP.

Importante: Cualquier propuesta de mejora o error detectado en el material de esta sesión de laboratorio hacedmela llegar. Gracias!

Trabajo a entregar

Como resultado de la práctica os pido un informe en el que recolectéis:

Resultados de rendimiento obtenidos comparados con la versión secuencial. Justificación
Opciones de compilación utlizadas
Número de threads utilizados
Respuesta a las preguntas que pudieran aparecer durante el presente guión
Resumen de los resultados y concluiones/justificación
Aquello que consideréis relevante destacar en el presente informe

Índice:

OpenMP
Entorno de trabajo
Estudo teórico-práctico de OpenMP
Análisis de programas y programación con OpenMP
Bibliografía

1. OpenMP

OpenMP [3] es un modelo portable de programación de aplicaciones paralelas en arquitecturas de memoria compartida. Ofrece a los programadores una versátil interfaz para el desarrollo de aplicaciones que se pueden ejecutar en plataformas que varían desde los computadores de sobremesa hasta los supercomputadores. La interfaz de programación de aplicación (API) en OpenMP soporta programación paralela de memoria compartida en Fortran y C/C++. Diferentes sistemas operativos soportan programas OpenMP (UNIX, Linux, Windows ...). En la documentación se incluye un extracto de la especificación de la API de OpenMP (versión 3.0, para C/C++ y Fortran) [5].

2. Entorno de trabajo

Los programas OpenMP de las prácticas 4 y 5 se compilarán y ejecutarán en el servidor de prácticas del Departamento de Informática e Ingeniería de Sistemas (DIIS), con nombre pilgor. Esta plataforma cuenta con dos procesadores Kunpeng de 48 cores cada uno:

pilgor - Huawei TaiShan 200 (Model 2280)

Linux 4.18.0-147.el8.aarch64 aarch64 GNU/Linux CentOS Linux 8.1.1911

CPU: 2xKunpeng 920-4826 48c 2.6 GHz L2 24MB L3 48MB, RAM: 320 GB

$prompt> lscpu //probar este comando para ver mas detalles

Se accede a la máquina mediante ssh al nombre pilgor.cps.unizar.es

3. Estudio teórico-práctico de OpenMP

A continuación se presenta un estudio de OpenMP que se basa en el publicado por el National Energy Research Scientific Computing Center (NERSC) [4]. Es un buen material para comprender tanto los modelos de programación y ejecución como las directivas básicas de OpenMP.

3.1. Modelo de ejecución

El API de OpenMP usa el modelo fork-join de ejecución paralela (ver Figura 1) . Un programa OpenMP comienza con un único thread, llamado master thread, que ejecuta el código de forma secuencial. Cuando el master thread se encuentra con una directiva OpenMP que indica el comienzo de una región paralela, crea un equipo (team) de threads y se convierte en el master thread del nuevo equipo. Las instrucciones del programa dentro de la región paralela son ejecutadas en paralelo por cada thread del equipo. Al finalizar la región paralela, los threads del equipo se sincronizan y sólo el master thread continúa con la ejecución del programa.

OpenMP Figura 1. Modelo de ejecución de OpenMP.

El número de threads creados al entrar en una región paralela puede controlarse por medio de una variable de entorno o por una función llamada desde el programa. Dentro de una región paralela puede definirse otra región paralela anidada en la cual cada thread de la región original se convierte en el master de su propio equipo de threads. El grado de paralelismo de un código OpenMP depende del propio código, del número de procesadores y del sistema operativo. En ningún caso se garantiza que cada thread se ejecute en un procesador diferente. Las directivas OpenMP, que tienen forma de comentarios Fortran o C/C++, se insertan en puntos clave del código fuente. En caso de que el compilador reconozca las directivas, generará el código necesario para paralelizar la región de código especificada.

3.2. Ejemplos

Los programas que contiene el estudio (C/C++), junto con varios scripts con órdenes de compilación y ejecución están en el presente repositorio, en la carpeta p4.

Las órdenes para clonar este repositorio en vuestro $HOME son:

git clone https://github.com/universidad-zaragoza/30237_MP.git

En general, para cada programa se realizarán las siguientes acciones:

Compilar con y sin soporte OpenMP (scripts compomp.sh y compnoomp.sh, echar un vistazo a las opciones de compilación).
Ejecutar la versión OpenMP y analizar aspectos de su ejecución (cómo se reparten las iteraciones de los bucles entre los threads, la ejecución de las distintas secciones de código ...). Es interesante ejecutar cada programa varias veces o variar el número de threads OpenMP (scriptejecuta.sh, dependiendo del shell que uses, igual tienes que modificarlo). Si es posible, ejecuta también la versión no-OpenMP y compara su salida con la versión OpenMP.

3.3. Directiva `parallel`

La directiva parallel define el inicio de una región paralela. Cuando el master thread se encuentra con esta directiva arranca un equipo de threads (fork) y cada uno de ellos ejecuta el code block. Al finalizar la región paralela (end parallel), los threads del equipo se sincronizan y sólo el masterthread continúa con la ejecución del programa (join).

#include <omp.h>

void main(){
  ...
  #pragma omp parallel [clause [clause [clause ... ]]]
  {
    // code block
  }
  ...
}

Entre otros aspectos, clause permite especificar si las variables de la región paralela serán privadas para cada thread o compartidas por el equipo.

Es importante recalcar que todo el código de la región paralela se ejecuta por cada uno de los threads del equipo, a menos que otra directiva OpenMP especifique lo contrario. Véase el siguiente ejemplo:

// hola.cpp
#include <iostream>
#include <omp.h>
int main()
{
    #pragma omp parallel
    {
        std::cout << "Hello " << omp_get_thread_num() << " ";
        std::cout << "World " << omp_get_thread_num() << std::endl;
    }
    return 0;
}

Asi pues, un bucle que se encuentre dentro de una región paralela se ejecutará al completo (de forma redundante) por cada thread a menos que se inserte una directiva for antes del bucle. Es necesaria una directiva for si se desea que las iteraciones de un bucle se repartan entre los threads de un equipo.

El siguiente código C++ muestra un ejemplo de uso de la directiva parallel:

// parallel.cpp
#include <iostream>
#include <sstream>
#include <string>

#include <omp.h>
int main()
{
    int i = 1;

    #pragma omp parallel firstprivate(i)
    {
    	//Opción 1
        //std::cout << i << "-" << omp_get_thread_num() << std::endl;
	//Opción 2
	//std::ostringstream buffer;
	//buffer << i << "-" << omp_get_thread_num() << std::endl;
	//std::cout << buffer.str();
	//Opción 2 bis
	std::cout <<  std::to_string(i) + "-" + std::to_string(omp_get_thread_num()) + "\n";
    }
    return 0;
}

Compila el programa. Puedes hacerlo directamente desde la línea de comandos:

pilgor:~/ g++ -O3 -fopenmp parallel.cpp -o parallelomp.bin

o con el script compfomp.sh:

pilgor:~/ ./compomp.sh parallel

El número máximo de threads que van a ejecutar un programa compilado para ejecución paralela con OpenMP se controla con la variable de entorno OMP_NUM_THREADS (Especificación OpenMP. Sección 6.2 [5]). Su valor por defecto suele ser 1, o incluso, sin definir. Las siguientes líneas muestran cómo cambiar el valor de la variable OMP_NUM_THREADS a 2 desde bash, ksh y csh:

$ export OMP_NUM_THREADS=2 # bash/ksh syntax
% setenv OMP_NUM_THREADS 2 # csh syntax

En el programa parallel.cppse proponen dos alternativas para imprimir por pantalla. La opción 1 permite que se entrelacen escrituras parciales de cada uno de los threads en ejecución, mientras que la opción 2 no.

En el capitulo 6 del documento de especificación "OpenMP Application Programming Interface" [5] se muestran las variables de entorno que controlan la ejecución de programas OpenMP.

Ejecuta parallel.cpp con distintos valores de OMP_NUM_THREADS. ¿Cuál es el número máximo de threads que soporta? Compila el programa sin soporte OpenMP, directamente desde la línea de comandos:

pilgor:~/ g++ -O3 parallel.cpp -o parallelnoomp.bin

o con el script compnoomp.sh:

pilgor:~/ ./compnoomp.sh parallel

Ejecuta esta versión del código y observa la salida.

3.3.1 Funciones de biblioteca OpenMP

El código parallel.cpp ilustra otro uso de la directiva parallel y el empleo de funciones de biblioteca OpenMP para obtener información de los threads en tiempo de ejecución. Compila parallel.c(compc.sh) y ejecútalo con distintos valores de OMP_NUM_THREADS. Observa y analiza la salida.

/* parallel2.cpp */
#include <omp.h>
#include <iostream>

int main(void){
  int i;

  #pragma omp parallel private(i)
  {
    i = omp_get_thread_num();
    if (i == 0)
      std::cout << "Soy el master thread (tid = " + std::to_string(i) + ")" << std::endl;
    else
      std::cout << "Soy el thread con tid " + std::to_string(i) << std::endl;
  }
  
  return 0;
}

El programa parallelmal.cpp es una variante de este programa que muestra el efecto de definir la variable i como compartida.

3.3.2 Paralelismo anidado

Una región paralela OpenMP puede estar anidada dentro de otra región paralela (por ejemplo, la segunda región paralela de la Figura 1). Si el paralelismo anidado está deshabilitado, entonces el nuevo equipo de threads creado por un thread que se encuentra con una directiva parallel dentro de una región paralela se compone sólo por ese mismo thread. Si el paralelismo anidado está habilitado, entonces el nuevo equipo puede componerse por más de un thread.

La biblioteca de ejecución de OpenMP mantiene una reserva de threads, thread pool, que pueden convertirse en threads de un equipo en regiones paralelas. Cuando un thread se encuentra con una directiva parallel y necesita crear un equipo de threads, busca en la citada reserva y se hace con threads ociosos, idle, que se convierten en trabajadores del equipo. El thread maestro puede obtener menos threads de los que necesita en caso de que no haya suficientes. Cuando el equipo de threads finaliza la ejecución de la sección paralela, los threads trabajadores vuelven a la reserva de threads.

El programa nested.cpp muestra un ejemplo de paralelismo anidado. Compila y ejecuta este programa. Analiza su salida sabiendo que, por defecto, el paralelismo anidado está deshabilitado. Puede activarse cambiando el valor de la variable de entorno OMP_MAX_ACTIVE_LEVELS a un valor positivo mayor que 1. Esta variable limita el número maximo operaciones de paralelismo anidado permitidas (Especificación OpenMP. Sección 6.8 [5]). Anteriormente esta característica estaba controlada por la variable de entorno OMP_NESTED. Y aunque el manual la califica como obsoleta, en la implementación de OpenMP de pilgor debe estar activa a true para que el paralelismo anidado esté habilitado. Se proponen los siguientes comandos:

pilgor:~$ export OMP_MAX_ACTIVE_LEVELS=valor_natural # valor > 0
pilgor:~$ export OMP_NESTED=true|false

Vuelve a ejecutar el programa y comprueba la diferencia. Modifica el programa para que varíe el número de threads que ejecutan cada una de las regiones paralelas. ¿Cuál es el número máximo de threads que llegas a ver?

/* nested.cpp */
#include <omp.h>
#include <iostream>

int main(void){
  int i;
  int nthreads, tnumber;

  omp_set_dynamic(???);
  //omp_set_max_active_levels(1);  // Sin anidamiento
  //omp_set_max_active_levels(5);  // Hasta 5 niveles de anidamiento
  omp_set_num_threads(2);

  #pragma omp parallel private(nthreads, tnumber)
  {
    tnumber = omp_get_thread_num();
    std::cout << "Primera región paralela: thread " + std::to_string(tnumber) + " de " + std::to_string(omp_get_num_threads()) << std::endl;

    omp_set_num_threads(4);

    #pragma omp parallel firstprivate(tnumber)
    {
      std::cout << "Región anidada paralela (Equipo " + std::to_string(tnumber) + "): thread " + std::to_string(omp_get_thread_num()) + " de " + std::to_string(omp_get_num_threads()) << std::endl;
    }
  }
  return 0;
}

3.3.3 Reducción

La claúsula (clause) reduction especifica un operador y una o más variables. Al comenzar la región paralela, se crea una copia privada de cada variable especificada para cada thread y se inicializa apropiadamente según el operador. Al finalizar la región paralela, las variables son actualizadas con los valores de sus copias privadas usando el operador especificado.

El programa reduction.cpp muestra el uso de reduction. Compílalo, ejecútalo con 2, 4 y 8 threads, y analiza su salida.

/* reduccion.cpp */
#include <omp.h>
#include <iostream>

int main(void){
  int i,j,k;
  int nthreads, tnumber;

  #pragma omp parallel private(tnumber) reduction(+:i) reduction (*:j) reduction (max:k)
  {
    tnumber = omp_get_thread_num();

    i = tnumber;
    j = tnumber;
    k = tnumber;

    std::cout << "Thread " + std::to_string(tnumber) + " I = " + std::to_string(i) + " J = " + std::to_string(j) + " K = " + std::to_string(k) << std::endl;

  }

  std::cout << "Thread " << tnumber << " I = " << i << " J = " << j << " K = " << k << std::endl;

}

3.4. Directiva `for`

La directiva for especifica que las iteraciones del bucle (for) que se encuentra inmediatamente a continuación deben repartirse entre los distintos threads del equipo. Esta directiva debe estar en una región paralela ya que por sí misma no crea los threads necesarios para ejecutar el bucle en paralelo.

#pragma omp for [clause[ [,] clause] ... ] new-line
  for-loops

Entre otros aspectos, las cláusulas permiten especificar si las variables del bucle serán privadas o compartidas, operaciones de reducción (Especificación OpenMP. Sección 2.9.2 [5]). También puede controlarse la forma de repartir las iteraciones del bucle entre los threads:

schedule(static[,chunk]): las iteraciones se dividen en bloques del tamaño especificado por chunk. Los bloques de iteraciones se asignan a los threads según el algoritmo round-robin.
schedule(dynamic[,chunk]): las iteraciones se dividen en bloques del tamaño especificado por chunk. Conforme cada thread finaliza su bloque de iteraciones, se le asigna dinámicamente el siguiente conjunto de iteraciones.
schedule(guided[,chunk]): las iteraciones se dividen en bloques cuyo tamaño decrece de forma exponencial, siendo chunk el tamaño más pequeño. Conforme cada thread finaliza su bloque de iteraciones, se le asigna dinámicamente el siguiente conjunto de iteraciones.
schedule(runtime): la planificación se retrasa hasta tiempo de ejecución. El tipo de planificación y el tamaño del bloque de iteraciones puede configurarse mediante la variable de entorno OMP_SCHEDULE. Algunos ejemplos para esta variable son:

setenv OMP_SCHEDULE "guided,4"
setenv OMP_SCHEDULE "dynamic"
setenv OMP_SCHEDULE "nonmonotonic:dynamic,4"

Compila el código fordir.cpp. Ejecútalo con 2 threads y analiza la salida. Verifica que las iteraciones del bucle se han repartido entre los 2 threads de la forma especificada en el código.

/* fordir.cpp */
#include <omp.h>
#include <iostream>
#include <random>
#include <algorithm>


unsigned const int DIM = 16;
double A[DIM], B[DIM], s;


int main(void){
  int i;
  int nthreads, tnumber;

  std::random_device rd;  // Se utilizará para sembrar el generador de aleatorios
  std::mt19937 gen(rd()); // Sembrado de  mersenne_twister_engine con rd()
  std::uniform_real_distribution<> dis(0.0, 100.0); //Configuración del espacio de de generación

  for (int n = 0; n < DIM; ++n) {
    A[n] = dis(gen);
    B[n] = dis(gen);
  }

  #pragma omp parallel private(nthreads,tnumber) shared(A,B)
  {
    #pragma omp for schedule (static,4)
    for (int n = 2; n < DIM; n++){
      B[n] = (A[n] - A[n-1]) / 2.0;
      nthreads = omp_get_num_threads();
      tnumber = omp_get_thread_num();
      std::cout << "Thread-" + std::to_string(tnumber) + " de " + std::to_string(nthreads) + " tiene N=" + std::to_string(n) << std::endl;
    } 
    
  }

  s = *std::max_element(B, B+DIM);
  auto l = std::max_element(B, B+DIM);
  std::cout << "Máximo gradiente: " << std::to_string(s) << " posicion: " << (l-B) << std::endl;

}

La siguiente tarea es modificar el tamaño de los bloques de iteraciones (chunks) que se reparten a los threads. Observa que efectivamente cambia la asignación de iteraciones. Prueba a ejecutar el programa con 8, 16 y 32 threads (tendrás que cambiar el valor de DIM). Por último, comenta las líneas correspondientes al #pragma omp for ... { } para observar que todos threads ejecutan el bucle completo.

3.5. Directiva `parallel for`

La directiva parallel for proporciona una forma abreviada de especificar una región paralela que contiene un bucle for.

#pragma omp parallel for [clause[ [,] clause] ... ] new-line
  for-loops

Su semántica es idéntica a la de una directiva parallel seguida de una directiva for, aunque algunas implementaciones pueden generar códigos diferentes.

El código parfor.cpp ilustra el uso de la directiva parallel for. También muestra el empleo de distintas funciones de tiempos para C++. Una de ellas, std::clock, mide el CPU time que corresponde al tiempo consumido por toda todo el proceso en la CPU. Sin embargo, std::chrono, contabiliza el wall time que corresponde con el tiempo real medido para la ejecución. Recordad que para medir el tiempo de un programa se puede utilizar el comando time, que se utiliza de la siguiente manera:

$pilgor: time comando_monitorizado

Compila parfor.cpp y ejecútalo con 1, 2, 4, 8, 16 y 32 threads. Analiza y anota los tiempos de ejecución. Calcula los distintos speedups y comenta los resultados.

/* parfor.cpp */
#include <omp.h>
#include <iostream>
#include <random>
#include <algorithm>
#include <ctime>
#include <chrono>
#include <cmath>

unsigned const int DIM1 = 50000, DIM2=20000;
double A[DIM1], B[DIM2][DIM1], C[DIM2][DIM1], s;
double * aux;

int main(void){
  clock_t t;
  int count1, count2, cr, i , j;
  double tarray1[2], tarray2[2];
  int nthreadsOMP, tnumber, maxnthreads, numprocsOMP;
  std::random_device rd;  // Se utilizará para sembrar el generador de aleatorios
  std::mt19937 gen(rd()); // Sembrado de  mersenne_twister_engine con rd()
  std::uniform_real_distribution<> dis(0.0, 100.0); //Configuración del espacio de de generación

  for (int n = 0; n < DIM1; ++n) {
    A[n] = dis(gen);
  }

  maxnthreads=omp_get_max_threads();
  numprocsOMP=omp_get_num_procs();

  //omp_set_dynamic(true);

  std::cout << "Entorno de Ejecución:" << std::endl;
  std::cout << " - Máximo nº de threads disponibles (omp_get_max_threads): " << maxnthreads << std::endl;
  std::cout << " - Nº de procesadores disponibles (omp_get_num_procs): " << numprocsOMP << std::endl;

  std::clock_t t_start1 = std::clock();
  auto t_start2 = std::chrono::high_resolution_clock::now();

  #pragma omp parallel for schedule(runtime) private(i,j) shared (A,B,C,nthreadsOMP)
  for (j=0; j<DIM2; j++){
    nthreadsOMP = omp_get_num_threads();
    for (i = 1; i<DIM1; i++){
      B[j][i] = ((A[i]+A[i-1])/2.0)/sqrt(A[i]);
      C[j][i] = sqrt(A[i]*2) / (A[i] - (A[i]/2.0));
      B[j][i] = C[j][i] * std::pow(B[j][i],2) * sin(A[i]);
    }
  }
  
  auto t_end2 = std::chrono::high_resolution_clock::now();
  std::clock_t t_end1 = std::clock();

  std::chrono::duration<double> elapsed_seconds2 = t_end2-t_start2;

  double *aux = (double *) B;
  s = *std::max_element(aux, aux + ((DIM2-1)*DIM1));
  
  std::cout << " - Threads utilizados (omp_get_num_threads): " << nthreadsOMP << std::endl;
  std::cout << "Chrono::high_resolution_clock, tiempo transcurrido: " << elapsed_seconds2.count() << std::endl;
  std::cout << "Time, tiempo transcurrido: " << (((float)(t_end1-t_start1))/CLOCKS_PER_SEC) << std::endl;

}

3.6. Directiva `sections`

La directiva sections define una región de código que contiene una serie de secciones de código que se deben repartir y ejecutar entre los threads de un equipo. Cada sección es ejecutada una vez por uno de los threads del equipo.

#pragma omp sections [clause[ [,] clause] ... ] new-line
 {
 [#pragma omp section new-line]
   structured-block
 [#pragma omp section new-line
   structured-block]
 ...
}

Compila el programa sections.cpp. Ejecútalo con 1, 2, 4 y 8 threads y observa su salida.

/* sections.cpp */
#include <omp.h>
#include <thread>
#include <chrono>
#include <iostream>

int main(void){
  int tnumber;
  #pragma omp parallel sections private(tnumber)
  {
    #pragma omp section 
    {
      tnumber = omp_get_thread_num();
      std::this_thread::sleep_for (std::chrono::seconds(1));
      std::cout << "Esta es la sección 1 ejecutada por el thread " + std::to_string(tnumber) << std::endl;
    }
    #pragma omp section
    {
      tnumber = omp_get_thread_num();
      std::this_thread::sleep_for (std::chrono::seconds(2));
      std::cout << "Esta es la sección 2 ejecutada por el thread " + std::to_string(tnumber) << std::endl;
    }
    #pragma omp section
    {
      tnumber = omp_get_thread_num();
      std::this_thread::sleep_for (std::chrono::seconds(2));
      std::cout << "Esta es la sección 3 ejecutada por el thread " + std::to_string(tnumber) << std::endl;
    }
    #pragma omp section
    {
      tnumber = omp_get_thread_num();
      std::this_thread::sleep_for (std::chrono::seconds(0));
      std::cout << "Esta es la sección 4 ejecutada por el thread " + std::to_string(tnumber) << std::endl;
    }
  }
}

3.7. Directiva `single`

La directiva single especifica que el código asociado debe ejecutarse solamente por un thread del equipo. Los threads que no ejecutan el código indicado por la directiva single deben esperar en la directiva end single (al final del bloque básico) a menos que se especifique nowait. No está permitido saltar (branch) al exterior desde un bloque de código ligado a la directiva single.

#pragma omp single [clause[ [,] clause] ... ] new-line
 structured-block

Compila, ejecuta con 4 threads y observa la salida del programa single.cpp. Luego prueba a comentar la directiva single.

/* single.cpp */
#include <omp.h>
#include <iostream>

const unsigned int DIM = 12000000;
double A[DIM], B[DIM], C[DIM], D[DIM];

int main(void){
  int tnumber;
  double summed = 0.0;

  #pragma omp parallel sections shared(A,B,C,D) 
  {
    #pragma omp section
    {
      for (int i=0; i < DIM; i++){
        A[i] = 1.0;
      }
    }
    #pragma omp section
    {
      for (int i=0; i < DIM; i++){
        B[i] = 1.0;
      }
    }
    #pragma omp section
    {
      for (int i=0; i < DIM; i++){
        C[i] = 1.0;
      }
    }
    #pragma omp section
    {
      for (int i=0; i < DIM; i++){
        D[i] = 1.0;
      }
    }
  }

  #pragma omp parallel shared(summed) 
  {
    #pragma omp single 
    {
      for (int i=0; i < DIM; i++){
        summed = summed + A[i];
        summed = summed + B[i];
        summed = summed + C[i];
      }
      std::cout << "Resultado de la suma es: " << summed << std::endl;
    } //los threads esperan aqui

    #pragma omp for schedule(static, 4)
    for (int i = 0; i < DIM; i++){
      D[i] =  A[i] + B[i] * C[i];
    }
  }

  for (int i = 0; i < 12; i++){
    std::cout << "D[" << i << "]="<< std::fixed <<D[i] << std::endl;
  }
}

3.8. Directiva `master`

El código asociado a la directiva master es ejecutado solamente por el thread maestro de un equipo. No hay barreras a la entrada o salida de la dicha sección de código. No está permitido saltar al exterior desde un bloque de código ligado a la directiva master.

#pragma omp master new-line
  structured-block

3.9. Directiva `barrier`

La directiva barrier sincroniza todos los threads de un equipo. Cuando un thread se encuentra con esta directiva, espera hasta que el resto de threads haya llegado a ese punto.

#pragma omp barrier new-line

Compila, ejecuta con 4 threads y observa la salida del programa barrier.cpp. Repite el mismo proceso tras comentar la línea #pragma omp barrier. ¿Podrías conseguir la misma funcionalidad con la directiva single?

/* barrier.cpp */
#include <omp.h>
#include <iostream>

const unsigned int DIM = 12;
double A[DIM], B[DIM], C[DIM], D[DIM];

int main(void){
  int l;
  int nthreads, tnumber;

  #pragma omp parallel shared (l) private(nthreads, tnumber)
  {
    nthreads = omp_get_num_threads();
    tnumber  = omp_get_thread_num();
    
    #pragma omp master
    {
      std::cout << "Escribe un valor:" << std::endl;
      std::cin >> l;
    }

    #pragma omp barrier

    #pragma omp critical
    {
      std::cout << "Mi numero de thread es: " << tnumber << std::endl;
      std::cout << "Numero de threads: " << nthreads << std::endl;
      std::cout << "Valor de L es: " << l << std::endl;
    }
  }  
}

3.10. Directiva `flush`

La directiva flush marca un punto de sincronización donde se requiere una visión consistente de memoria. La lista de argumentos contiene las variables que deben ser enviadas (flush) a memoria para evitar realizar esa tarea con todas las variables del código.

#pragma omp flush [memory-order-clause] [(list)] new-line

3.11. Directiva `atomic`

La directiva atomic asegura que una dirección específica de memoria sea actualizada atómicamente, evitando así su exposición a múltiples escrituras por parte de distintos threads.

#pragma omp atomic [clause[[[,] clause] ... ] [,]] atomic-clause
  [[,] clause [[[,] clause] ... ]] new-line
  expression-stmt

Compila, ejecuta con 4 threads y observa la salida del programa histogram.cpp.

/* histogram.cpp */
#include <omp.h>
#include <iostream>
#include <random>

const unsigned int DIM = 100000;
int A[DIM];
int histogram[10]={0,0,0,0,0,0,0,0,0,0};
int histogram2[10]={0,0,0,0,0,0,0,0,0,0};

int main(void){
  int l,i;
  int nthreads, tnumber;

  std::random_device rd;  // Se utilizará para sembrar el generador de aleatorios
  std::mt19937 gen(rd()); // Sembrado de  mersenne_twister_engine con rd()
  std::uniform_real_distribution<> dis(1,10); //Configuración del espacio de de generación

  for (int n = 0; n < DIM; ++n) {
    A[n] = dis(gen);
  }

  #pragma omp parallel for
  for(i=0; i<DIM; i++){
    //#pragma omp atomic
    histogram[A[i]]++;
  }

  for (i = 0; i < DIM; i++){
    histogram2[A[i]]++;
  }

  for (i = 0; i < 10; i++){
    std::cout << histogram[i] << " - " << histogram2[i];
    if (histogram[i] != histogram2[i]){
      std::cout << " ERROR";
    }
    std::cout << std::endl;
  }
}

Sin las directivas atomic, varios threads podrían tratar de actualizar la variable histogram al mismo tiempo, causando resultados erróneos. Recompila y reejecuta el código tras comentar la directiva atomic. Observa como falla el calculo del histograma.

3.12. Directiva `ordered`

El código de un bucle asociado a una directiva ordered se ejecuta en el mismo orden que lo haría si las iteraciones se ejecutaran de forma secuencial. La directiva ordered sólo puede aparecer en el contexto de una directiva for o parallel for. No está permitido saltar (branch) al exterior desde un bloque de código ligado a la directiva ordered.

#pragma omp ordered [clause[ [,] clause] ] new-line
  structured-block

Compila, ejecuta con 4 threads y observa la salida del programa ordered.cpp. Repite el mismo proceso tras comentar las directivas ordered.

/* ordered.cpp */
#include <omp.h>
#include <iostream>
#include <random>

const unsigned int N = 1000, M = 4000;
double X[N][M], Y[M][N], Z[N];

int main(void){
  int j,i;
  int nthreads, tnumber;

  std::random_device rd;  // Se utilizará para sembrar el generador de aleatorios
  std::mt19937 gen(rd()); // Sembrado de  mersenne_twister_engine con rd()
  std::uniform_real_distribution<> dis(0.0, 1.0); //Configuración del espacio de de generación

  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < M; ++j) {
      X[i][j] = dis(gen);
      Y[j][i] = dis(gen);
    }
    Z[i] = 0.0;
  }

  #pragma omp parallel default(shared) private (i,j)
  {
    #pragma omp for schedule(dynamic, 2) ordered
    for ( i=0 ; i < N; ++i){
      for ( j=0; j < M; ++j){
        Z[i] = Z[i] + X[i][j] * Y[j][i];
      }
      #pragma omp ordered
      if(i<21){
        std::cout << "Z[" << i << "]="<< Z[i] << std::endl;
      }
    }
  }
}

4. Análisis de programas y programación con OpenMP

En los siguientes subapartados se plantean unos códigos que contienen bucles. En todos los casos hay un bucle de inicialización y otro de trabajo. Descartaremos los bucles de inicialización y nos centraremos en los bucles de trabajo. Algunos de estos bucles son susceptibles de ser ejecutados en paralelo y otros tienen dependencias que impiden su paralelización. El trabajo consiste en analizar los bucles y, en aquellos casos que sea posible, insertar las directivas de compilación OpenMP adecuadas. Después se compilarán dichos programas en secuencial y paralelo y finalmente se ejecutarán para verificar la corrección de las directivas insertadas.

Los programas que utilizaremos en los experimentos y los scripts para su compilación los podréis encontrar en la carpeta parte2 del repositorio de la práctica.

4.1. Análisis de dependencias

El análisis de dependencias es una técnica necesaria para extraer paralelismo. Se inspecciona si dos o más referencias acceden a la misma posición de memoria. Si sucede tal hecho, al menos una de las referencias es una escritura, y pertenece a una iteración distinta a la de las lecturas, entonces el bucle no puede ser ejecutado en paralelo (dependencia entre iteraciones).

Teniendo esto en cuenta, analiza los programas ejer2a, ejer2b y ejer2c, indica cuál de sus bucles principales (no los de inicialización) puede paralelizarse e inserta las directivas OpenMP adecuadas. Comprueba tus respuestas comparando los resultados de las versiones secuencial y paralela de los programas.

Otra alternativa consiste en indicarle al compilador que analice el código y genere código paralelo en los bucles for. Las dos opciones que debéis tener en cuenta son : '-floop-parallelize-all y -ftree-parallelize-loops=n'. Busca su descripción en el manual del compilador. Para saber mas sobre la generación automática de código paralelo en GCC, podéis empezar por el siguiente enlace Graphite.

Nota: echa un vistazo a los scripts 'compomp.sh' y 'compnoomp.sh' disponibles en el directorio 'parte2' del repositorio.

Ejercicio 2.a

/* ordered.cpp */
#include <omp.h>
#include <iostream>
#include <random>

const unsigned int N = 1000000;
double A[N], B[N], C[N];

int main(void){
  int nthreads, tnumber;

  std::random_device rd;  // Se utilizará para sembrar el generador de aleatorios
  std::mt19937 gen(rd()); // Sembrado de  mersenne_twister_engine con rd()
  std::uniform_real_distribution<> dis(0.0, 100.0); //Configuración del espacio de de generación

  for (int i = 0; i < N; ++i) {
    A[i] = dis(gen);
    B[i] = dis(gen);
    C[i] = 0.0;
  }
  
  for (int i = 0; i < N; ++i) {
    A[i] = A[i] + B[i]/2.0;
  }
  
  for (int i=0 ; i < N; ++i){
    A[2*i] = B[i];
    C[2*i] = A[2*i];
    C[2*i + 1] = A[2*i + 1];
  }
  
  std::cout << "A[150]=" << A[150] << " B[150]=" << B[150] << "C[150]=" << C[150] << std::endl;
}

Ejercicio 2.b

/* ejer2b.cpp */
#include <omp.h>
#include <iostream>
#include <random>

const unsigned int N = 1000000;
double A[N], B[N];

int main(void){
  int nthreads, tnumber;

  std::random_device rd;  // Se utilizará para sembrar el generador de aleatorios
  std::mt19937 gen(rd()); // Sembrado de  mersenne_twister_engine con rd()
  std::uniform_real_distribution<> dis(0.0, 100.0); //Configuración del espacio de de generación

  for (int i = 0; i < N; ++i) {
    A[i] = dis(gen);
  }
  
  for (int i = 1; i < N; ++i) {
    B[i] = A[i] - A[i-1];
  }
  
  std::cout << "A[150]=" << A[150] << "A[149]=" << A[149] << "B[150]=" << B[150] << std::endl;

}

Ejercicio 2.c

/* ejer2c.cpp */
#include <omp.h>
#include <iostream>
#include <random>

const unsigned int N = 1000000;
double A[N];

int main(void){
  int nthreads, tnumber;

  std::random_device rd;  // Se utilizará para sembrar el generador de aleatorios
  std::mt19937 gen(rd()); // Sembrado de  mersenne_twister_engine con rd()
  std::uniform_real_distribution<> dis(0.0, 100.0); //Configuración del espacio de de generación

  for (int i = 0; i < N; ++i) {
    A[i] = dis(gen);
  }
  
  for (int i = 1; i < N; ++i) {
    A[i] = A[i] - A[i-1];
  }
  
  std::cout << "A[150]=" << A[150] << std::endl;

}

4.2. Privatización

Existen transformaciones que eliminan las dependencias falsas (dependencias de salida y antidependencias). Por ejemplo, en el código ejer3a, todas las iteraciones del bucle principal escriben y leen la variable t, así que existen dependencias entre iteraciones (lcd, loop carried dependences). Sin embargo, cada iteración utiliza el valor de t como almacén de un valor temporal que no se emplea en las demás iteraciones. Esta dependencia puede eliminarse dando a cada iteración una copia de t. A esta técnica se le denomina expansión escalar, la dimensión de la variable expandida es igual a la del resto de estructura de datos. Alternativamente, puede indicarse que sólo es necesaria una copia de tpor thread, esta técnica se denomina privatización, y está soportada por OpenMP.

Considerando lo anterior, analiza los programas ejer3a y ejer3b, indica qué bucles pueden paralelizarse e inserta las directivas OpenMP adecuadas. Comprueba tus respuestas comparando los resultados de las versiones secuencial y paralela de los programas.

Ejercicio 3.a

/* ejer3a.cpp */
#include <omp.h>
#include <iostream>
#include <random>
#include <math.h>

const unsigned int N = 1000000;
double A[N], B[N], C[N];

int main(void){
  int nthreads, tnumber;
  double t;
  std::random_device rd;  // Se utilizará para sembrar el generador de aleatorios
  std::mt19937 gen(rd()); // Sembrado de  mersenne_twister_engine con rd()
  std::uniform_real_distribution<> dis(0.0, 100.0); //Configuración del espacio de de generación

  for (int i = 0; i < N; ++i) {
    A[i] = dis(gen);
  }
  
  for (int i = 1; i < N; ++i) {
    t = A[i];
    B[i] = t + pow(t, 2);
    C[i] = t + 2.0;
  }
  
  std::cout << "B[150]=" << B[150] << "C[150]=" << C[150] << "A[150]=" << A[150] << std::endl;

}

Ejercico 3.b

/* ejer3b.cpp */
#include <omp.h>
#include <iostream>
#include <random>
#include <math.h>

const unsigned int N = 10000;
double A[N][N], B[N][N], C[N][N], t[N];

int main(void){
  int nthreads, tnumber;

  std::random_device rd;  // Se utilizará para sembrar el generador de aleatorios
  std::mt19937 gen(rd()); // Sembrado de  mersenne_twister_engine con rd()
  std::uniform_real_distribution<> dis(0.0, 100.0); //Configuración del espacio de de generación

  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j){
      A[i][j] = dis(gen);
      B[i][j] = dis(gen);
      C[i][j] = dis(gen);
    }
  }

  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j){
      t[j] = A[i][j] + B[i][j];
      C[i][j] = t[j] + C[i][j];
    }
  }
  
  std::cout << "B[150][150]=" << B[150][150] << "C[150][150]=" << C[150][150] << "A[150][150]=" << A[150][150] << std::endl;

}

4.3. Sustitución de variables de inducción

La presencia de variables de inducción (variables enteras que son modificadas en cada iteración de un bucle) impide la paralelización de un bucle por dos razones: la variable de inducción es leída y escrita en cada iteración, por tanto genera dependencia entre iteraciones. Además, la referencia a un vector/matriz indexado/a por tales variables impide el correcto análisis del bucle. Para evitar estos problemas, algunos compiladores transforman la variable de inducción y la sustituyen por una expresión dependiente del índice del bucle. Teniendo esto en cuenta, analiza el programa ejer4a, indica si el bucle principal puede paralelizarse e inserta las directivas OpenMP adecuadas. Comprueba tu respuesta comparando los resultados de las versiones secuencial y paralela.

4.4. Reducción

La reducción opera sobre un vector o matriz y produce una variable de dimensión menor. Una reducción causa dependencias entre iteraciones. En algunos casos, este bucle puede paralelizarse, aunque el nivel dinámico de paralelismo se reducirá exponencialmente. Analiza el programa ejer5, indica si su bucle principal puede paralelizarse e inserta las directivas OpenMP adecuadas. Verifica tu respuesta comparando los resultados de las versiones secuencial y paralela.

Ejercicio 4.a

/* ejer4a.cpp */
#include <omp.h>
#include <iostream>
#include <random>

const unsigned int N = 1000000;
double A[N], B[N];

int main(void){
  int nthreads, tnumber;
  int i, j;

  std::random_device rd;  // Se utilizará para sembrar el generador de aleatorios
  std::mt19937 gen(rd()); // Sembrado de  mersenne_twister_engine con rd()
  std::uniform_real_distribution<> dis(0.0, 100.0); //Configuración del espacio de de generación

  for (i = 0; i < N; ++i) {
    A[i] = dis(gen);
  }

  j = 0;

  for (i = 0; i < (N/2)-1; ++i) {
    j = j + 2;
    B[j] = A[i];
  }
   
  std::cout << "B[152]=" << B[152] << " A[150]=" << A[150] << std::endl;

}

Ejercicio 5

/* ejer5.cpp */
#include <omp.h>
#include <iostream>
#include <random>

const unsigned int N = 1000000;
double A[N], B[N], q;

int main(void){
  int nthreads, tnumber;
  int i, j;

  std::random_device rd;  // Se utilizará para sembrar el generador de aleatorios
  std::mt19937 gen(rd()); // Sembrado de  mersenne_twister_engine con rd()
  std::uniform_real_distribution<> dis(0.0, 100.0); //Configuración del espacio de de generación

  for (i = 0; i < N; ++i) {
    A[i] = dis(gen);
    B[i] = dis(gen);
  }

  for (int i = 0; i < N; ++i) {
    A[i] = A[i] + B[i];
    q = q + A[i];
  }  
 
  std::cout << "B[150]=" << B[150] << " A[150]=" << A[150] << " q=" << q << std::endl;

}

#5. Bibliografía

Bibliografía

[3] Sitio web oficial de OpenMP: http://www.openmp.org

[4] Tutorial de OpenMP: http://www.nersc.gov/nusers/help/tutorials/openmp/

[5] API de OpenMP (versión 5.0): https://www.openmp.org/wp-content/uploads/OpenMP-API-Specification-5.0.pdf

Rudolf Eigenmann, Jay Hoeflinger. “Parallelizing and Vectorizing Compilers”. Purdue Univ. School of ECE, High-Performance Computing Lab.ECE-HPCLab-99201, Jan 2000.
Técnicas de análisis y transformación de código para la vectorización y extracción de paralelismo. Incluye una interesante introducción y clasificación de arquitecturas y modelos de lenguajes paralelos. Se entrega con la documentación de la práctica. William Blume, Ramon Doallo, Rudolf Eigenmann, John Grout, Jay Hoeflinger, Thomas Lawrence, Jaejin Lee, David Padua, Yunheung Paek, Bill Pottenger, Lawrence Rauchwerger, and Peng Tu. "Advanced Program Restructuring for High-Performance Computers with Polaris", (short version of this paper was published in IEEE Computer, December 1996, pp 78-82)

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Práctica 4: Paralelización con OpenMP

Práctica 4: Programación paralela con OpenMP

Resumen

Trabajo a entregar

Índice:

1. OpenMP

2. Entorno de trabajo

3. Estudio teórico-práctico de OpenMP

3.1. Modelo de ejecución

3.2. Ejemplos

3.3. Directiva `parallel`

3.3.1 Funciones de biblioteca OpenMP

3.3.2 Paralelismo anidado

3.3.3 Reducción

3.4. Directiva `for`

3.5. Directiva `parallel for`

3.6. Directiva `sections`

3.7. Directiva `single`

3.8. Directiva `master`

3.9. Directiva `barrier`

3.10. Directiva `flush`

3.11. Directiva `atomic`

3.12. Directiva `ordered`

4. Análisis de programas y programación con OpenMP

4.1. Análisis de dependencias

Ejercicio 2.a

Ejercicio 2.b

Ejercicio 2.c

4.2. Privatización

Ejercicio 3.a

Ejercico 3.b

4.3. Sustitución de variables de inducción

4.4. Reducción

Ejercicio 4.a

Ejercicio 5

Bibliografía

Clone this wiki locally

Práctica 4: Paralelización con OpenMP

Práctica 4: Programación paralela con OpenMP

Resumen

Trabajo a entregar

Índice:

1. OpenMP

2. Entorno de trabajo

3. Estudio teórico-práctico de OpenMP

3.1. Modelo de ejecución

3.2. Ejemplos

3.3. Directiva parallel

3.3.1 Funciones de biblioteca OpenMP

3.3.2 Paralelismo anidado

3.3.3 Reducción

3.4. Directiva for

3.5. Directiva parallel for

3.6. Directiva sections

3.7. Directiva single

3.8. Directiva master

3.9. Directiva barrier

3.10. Directiva flush

3.11. Directiva atomic

3.12. Directiva ordered

4. Análisis de programas y programación con OpenMP

4.1. Análisis de dependencias

Ejercicio 2.a

Ejercicio 2.b

Ejercicio 2.c

4.2. Privatización

Ejercicio 3.a

Ejercico 3.b

4.3. Sustitución de variables de inducción

4.4. Reducción

Ejercicio 4.a

Ejercicio 5

Bibliografía

Clone this wiki locally

3.3. Directiva `parallel`

3.4. Directiva `for`

3.5. Directiva `parallel for`

3.6. Directiva `sections`

3.7. Directiva `single`

3.8. Directiva `master`

3.9. Directiva `barrier`

3.10. Directiva `flush`

3.11. Directiva `atomic`

3.12. Directiva `ordered`