Práctica 5: Paralelización automática y mediante directivas OpenMP

Resumen

En esta práctica se analizará una solución al problema del cálculo del número π. El código que implementa el cálculo se compilará de tres formas según distintos objetivos: ejecución serie, paralelización automática por parte del compilador y paralelización mediante directivas OpenMP. También se medirán tiempos de ejecución de los distintos ejecutables para calcular aceleraciones (speedups) y rendimiento (MFLOPS).

Introducción
Análisis de las dependencias del código
Ejecución secuencial
Ejecución paralela
Bibliografía

pi (1)

Figura 1: Aproximación para el cálculo de π

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

1. Introducción

En esta práctica se va a calcular una aproximación del número π mediante la siguiente ecuación:

formulapi

Para resolver la integral se divide el dominio [0, 1] en intervalos, se calcula el valor de la función 4/(1 + x^2) en el punto medio de cada intervalo y después se multiplican dichos valores por la anchura de cada rectángulo. Finalmente se suman las áreas de todos los rectángulos para obtener un valor aproximado de π. Por ejemplo, el área de los 10 rectángulos mostrados en la figura 1 aproximan esta integral.

Se proporciona el código C++ que implementa este cálculo de π. En concreto, se presentan distintas versiones orientadas a la ejecución serie (con y sin desenrollado), paralela (paralelización automática por parte del compilador) y plantilla para la paralelización manual mediante directivas OpenMP. Su ubicación es la misma que para la práctica 4 de la asignatura. La órden para clonar este repositorio en vuestro $HOME es:

git clone https://github.com/universidad-zaragoza/Multiprocesadores.git

En esta práctica 5, el material para la primera parte lo encontraréis en el directorio p5/pi.

2. Análisis de las dependencias del código

El siguiente algoritmo realiza la aproximación de π con nsubinterval rectángulos:

void main(int argc, char *argv){
  int nsubintervals; // numero de subintervalos en que se divide el intervalo [0,1]
  double subinterval, x;
  double area = 0.0;

  nsubinterval = atoi(argv[1]);
  subinterval =  1.0 / nsubintervals;

  for (int i = 0; i < nsubintervals; i++){
    x = (i-0.5)*subinterval;  // S1
    area = area + 4.0/(1.0 + x*x);   // S2
  }
  std::cout << "Valor de pi aproximado: " << area << std::endl;
}

Analiza las dependencias de este código con especial énfasis en las sentencias S1 y S2.

3. Ejecución secuencial

3.1. Experimento 1: Programa Serie

#include <iostream>
#include <ctime>
#include <chrono>
#include <limits>
#include <iomanip>

int main(int argc, char **argv){
  double nsubintervals = 100000000;
  double x, pi, area, subinterval;
  long int i;
  int count1, count2, cr;

  if (argc == 2){
    nsubintervals = atof(argv[1]);
  }
  
  std::cout << "Nº de procesadores: 1" << std::endl;
  std::cout << "Nª de threads: 1" << std::endl;
  std::cout << "Resolución de los relojes:" << std::endl;
  std::cout << " - system_clock(std::clock): " << 1e6/CLOCKS_PER_SEC << " us -- " << CLOCKS_PER_SEC/1e6 << " MHz" << std::endl;

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

  subinterval = 1.0 / nsubintervals;
  area = 0.0;

  for (i = 0; i < nsubintervals; i++){
    double x = (i-0.5)*subinterval;  // S1
    area = area + 4.0/(1.0 + x*x);   // S2
  }

  pi = subinterval*area;

  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;

  std::cout << "***************************************" << std::endl;
  std::cout << " PIcalculado =" << std::setprecision(18) << pi << std::endl;
  std::cout << " PIreal = 3.1415926535897932385" << std::endl;
  std::cout << std::endl;
  std::cout << "*** tiempos ***" << std::endl;
  std::cout << "CPU clock = " << (((float)(t_end1-t_start1))/CLOCKS_PER_SEC) << " sg" << std::endl;
  std::cout << "Wall Clock = " << elapsed_seconds2.count() << " sg" << std::endl;
  std::cout << "-----------------------------------------" << std::endl;

}

Compila el código pi_serie.cpp en pilgor:

$ g++ -g -O0 pi_serie.cpp -o pi_serie

Las opciones de compilación se describen en la documentación del compilador $> man g++.

A falta de informe de compilación, observa las anotaciones del código fuente generadas por el compilador:

$> objdump -drwCS pi_serie

Las opciones del comando objdump pueden ser consultadas en las páginas de ayuda '$> man objdump`.

Localiza el bucle principal de la aplicación y estudia el código ensamblador generado. Compáralo con el generado cuando se utiliza la opción de compilación -O3.

Ejecuta los binarios generados para -O0 y -O3. Anota su tiempo de ejecución y calcula los MFLOPS alcanzados.

3.2. Experimento 2: Desenrollado de bucle

#include <iostream>
#include <ctime>
#include <chrono>
#include <limits>
#include <iomanip>

int main(int argc, char **argv){
  double nsubintervals = 100000000;
  double x, pi, varea[4], subinterval;
  long int i;
  int count1, count2, cr;

  if (argc == 2){
    nsubintervals = atof(argv[1]);
  }
  
  std::cout << "Nº de procesadores: 1" << std::endl;
  std::cout << "Nª de threads: 1" << std::endl;
  std::cout << "Resolución de los relojes:" << std::endl;
  std::cout << " - system_clock(std::clock): " << 1e6/CLOCKS_PER_SEC << " us -- " << CLOCKS_PER_SEC/1e6 << " MHz" << std::endl;

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

  subinterval = 1.0 / nsubintervals;
  varea[0] = 0.0;
  varea[1] = 0.0;
  varea[2] = 0.0;
  varea[3] = 0.0;

  for (i = 0; i < nsubintervals; i+=4){
    x = (i-0.5)*subinterval;  
    varea[0] = varea[0] + 4.0/(1.0 + x*x);   
    x = (i+0.5)*subinterval;  
    varea[1] = varea[1] + 4.0/(1.0 + x*x);   
    x = (i+1.5)*subinterval;  
    varea[2] = varea[2] + 4.0/(1.0 + x*x);   
    x = (i+2.5)*subinterval;  
    varea[3] = varea[3] + 4.0/(1.0 + x*x);   
  }

  pi = subinterval * (varea[0] + varea[1] + varea[2] + varea[3]);

  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;

  std::cout << "***************************************" << std::endl;
  std::cout << " PIcalculado =" << std::setprecision(18) << pi << std::endl;
  std::cout << " PIreal = 3.1415926535897932385" << std::endl;
  std::cout << std::endl;
  std::cout << "*** tiempos ***" << std::endl;
  std::cout << "CPU clock = " << (((float)(t_end1-t_start1))/CLOCKS_PER_SEC) << " sg" << std::endl;
  std::cout << "Wall Clock = " << elapsed_seconds2.count() << " sg" << std::endl;
  std::cout << "-----------------------------------------" << std::endl;

}

Compila el programa pi_unroll4.cpp con las mismas opciones que el programa anterior. Inspecciona con objdump el código generado y comprueba que el mismo coincide con el fuente utilizado.

Ejecuta el binario generado. A partir del tiempo de ejecución, calcula el rendimiento en MFLOPS y la mejora (speedup) respecto el código del experimento 1, hazlo tanto para O0 como para O3. Justifica los resultados obtenidos.

3.3. Experimento 3: reducción del número de operaciones

El algoritmo puede ejecutarse efectuando menos operaciones de coma flotante. Para ello, aplicamos una optimización manual: el valor de x al comienzo de cada iteración se calcula a partir del su valor en la iteración anterior. El código resultante del bucle se muestra a continuación:

#include <iostream>
#include <ctime>
#include <chrono>
#include <limits>
#include <iomanip>

int main(int argc, char **argv){
  double nsubintervals = 100000000;
  double x, pi, varea[4], subinterval;
  long int i;
  int count1, count2, cr;

  if (argc == 2){
    nsubintervals = atof(argv[1]);
  }
  
  std::cout << "Nº de procesadores: 1" << std::endl;
  std::cout << "Nª de threads: 1" << std::endl;
  std::cout << "Resolución de los relojes:" << std::endl;
  std::cout << " - system_clock(std::clock): " << 1e6/CLOCKS_PER_SEC << " us -- " << CLOCKS_PER_SEC/1e6 << " MHz" << std::endl;

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

  subinterval = 1.0 / nsubintervals;
  varea[0] = 0.0;
  varea[1] = 0.0;
  varea[2] = 0.0;
  varea[3] = 0.0;

  x = 0.5 * subinterval;
  
  for (i = 0; i < nsubintervals; i+=4){
    varea[0] = varea[0] + 4.0/(1.0 + x*x);   
    x = x + subinterval;  
    varea[1] = varea[1] + 4.0/(1.0 + x*x);   
    x = x + subinterval;  
    varea[2] = varea[2] + 4.0/(1.0 + x*x);   
    x = x + subinterval;  
    varea[3] = varea[3] + 4.0/(1.0 + x*x);   
    x = x + subinterval;  
  }

  pi = subinterval * (varea[0] + varea[1] + varea[2] + varea[3]);

  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;

  std::cout << "***************************************" << std::endl;
  std::cout << " PIcalculado =" << std::setprecision(18) << pi << std::endl;
  std::cout << " PIreal = 3.1415926535897932385" << std::endl;
  std::cout << std::endl;
  std::cout << "*** tiempos ***" << std::endl;
  std::cout << "CPU clock = " << (((float)(t_end1-t_start1))/CLOCKS_PER_SEC) << " sg" << std::endl;
  std::cout << "Wall Clock = " << elapsed_seconds2.count() << " sg" << std::endl;
  std::cout << "-----------------------------------------" << std::endl;

}

Compila el programa pi_unroll4_reduccion.cpp con las mismas opciones que el programa anterior. Inspecciona con objdump el código generado y comprueba que el mismo coincide con el fuente utilizado.

Ejecuta el binario generado. A partir del tiempo de ejecución, calcula el rendimiento en MFLOPS y la mejora (speedup) respecto el código del experimento 1, hazlo tanto para O0 como para O3. Justifica los resultados obtenidos.

4. Ejecución paralela

4.1. Paralelización automática por parte del compilador

Compila el código pi.cpp con las opciones necesarias para que el bucle de cálculo se paralelice de forma automática y la salida del compilador muestre los bucles paralelizados. Tendrás que buscar dichas opciones en la documentación de GCC ($> man gcc).

Analiza la salida del compilador y comprueba la salida de los informes de compilación que se pueden generar: -fdump-tree-???y -fopt-info-???. Una vez paralelizado puedes analizar la salida de objdump para comprobar los cambios introducidos por el paralelizador autmatico.

Recuerda que, tal y como vimos en la práctica 4, el módulo encargado de analizar las dependencias de datos y en el se fundamenta la generación automática de código en gcc es Graphite. La capacidad de análisis de Gcc es bastante limitada y deberás tranformar el código fuente para superar esas limitaciones. Deberás seguir un proceso iterativo en el que el reporte de compilación indique dónde se encuentra la limitación y proceder a una transformación de código que permita paralelizar algo del trabajo.

Ejecuta el programa utilizando 1, 2, 4, 8, 16 y 32 threads. R

Al respecto de los tiempos de ejecución observados:

¿Cuál es la diferencia entre los tiempos que devuelven las funciones std::...::now y std::...::clock ?
Compara el tiempo de ejecución de 1 thread con el obtenido por la versión secuencial (experimento 1).
Calcula el rendimiento en MFLOPS alcanzado en cada ejecución.
Calcula las aceleraciones (speedups) respecto a la ejecución de este código con 1 procesador.
Trata de relacionar los speedups con las características de pilgor.

#include <iostream>
#include <ctime>
#include <chrono>
#include <limits>
#include <iomanip>

int main(int argc, char **argv){
  long int nsubintervals = 100000000;
  double x, pi, area, subinterval;
  long int i;
  int count1, count2, cr;

  if (argc == 2){
    nsubintervals = atof(argv[1]);
  }
  
  std::cout << "Nº de procesadores: 1" << std::endl;
  std::cout << "Nª de threads: 1" << std::endl;
  std::cout << "Resolución de los relojes:" << std::endl;
  std::cout << " - system_clock(std::clock): " << 1e6/CLOCKS_PER_SEC << " us -- " << CLOCKS_PER_SEC/1e6 << " MHz" << std::endl;

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

  subinterval = 1.0 / nsubintervals;
  area = 0.0;
  
  for (i = 0; i < nsubintervals; i++){
    x = (i-0.5)*subinterval;  
    area = area + (4.0/(1.0 + x*x));
  }

  pi = subinterval*area;

  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;

  std::cout << "***************************************" << std::endl;
  std::cout << " PIcalculado =" << std::setprecision(18) << pi << std::endl;
  std::cout << " PIreal = 3.1415926535897932385" << std::endl;
  std::cout << std::endl;
  std::cout << "*** tiempos ***" << std::endl;
  std::cout << "CPU clock = " << (((float)(t_end1-t_start1))/CLOCKS_PER_SEC) << " sg" << std::endl;
  std::cout << "Wall Clock = " << elapsed_seconds2.count() << " sg" << std::endl;
  std::cout << "-----------------------------------------" << std::endl;

}

4.2. Paralelización manual mediante directivas OpenMP

En este último experimento debes especificar de forma manual el paralelismo existente en el bucle principal del programa. Para ello se utilizarán directivas OpenMP en el fichero fuente pi_openmp.cpp.

#include <iostream>
#include <ctime>
#include <chrono>
#include <limits>
#include <iomanip>
#include <omp.h>

int main(int argc, char *argv[]){
  double nsubintervals = 100000000;
  double x, pi, area, subinterval;
  int i, count1, count2, cr;
  
  int maxnthreadsOMP = omp_get_max_threads();
  int nprocsOMP = omp_get_num_procs();
  
  if (argc == 2){
    nsubintervals = atof(argv[1]);
  }

  double wtr = omp_get_wtick();

  std::cout << "Nº de procesadores" << std::endl;
  std::cout << " - omp_get_num_procs: " << nprocsOMP << std::endl;
  std::cout << "Nº de threads" << std::endl;
  std::cout << " - omp_get_max_threads: " << maxnthreadsOMP << std::endl;
  std::cout << "Resolucion de relojes:" << std::endl;
  std::cout << " - system_clock: " << 1e6/cr << " usg-> " << cr/1e6 << " MHz" << std::endl;
  std::cout << " - omp_get_wtick: " << 1e6*wtr << " usg-> " << 1.0/(1e6*wtr) << " MHz" << std::endl;

  std::cout << "Calculando pi (nº intervalos " << nsubintervals << ")" << std::endl;

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

  for (int i = 0; i < nsubintervals; i++){
    // threadID = omp_get_thread_num();
    // std::cout << "Thread " << threadID << " : iteración " << i << std::endl;
    x = (i-0.5)*subinterval;  // S1
    area = area + 4.0/(1.0 + x*x);   // S2
  }

  double wtime2 = omp_get_wtime();

  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;

  std::cout << "***************************************" << std::endl;
  std::cout << " PIcalculado =" << pi << std::endl;
  std::cout << " PIreal = 3.1415926535897932385" << std::endl;
  std::cout << std::endl;
  std::cout << "*** tiempos ***" << std::endl;
  std::cout << "CPU clock = " << (((float)(t_end1-t_start1))/CLOCKS_PER_SEC) << std::endl;
  std::cout << "Wall Clock = " << elapsed_seconds2.count() << std::endl;
  std::cout << "OMP time = " << wtime2 - wtime1 << " sg" << std::endl;
  std::cout << "-----------------------------------------" << std::endl;
 
}

Inserta las directivas OpenMP correspondientes en el fuente original del apartado anterior (en torno al bucle principal).

Compila el código y analiza el código resultante para el bucle principal con objdump, así mismo, estudia y analizar brevemente los resultados de los infomes de compilación.

Ejecuta el programa utilizando 1, 2, 4, 8, 16 y 32 threads. A partir de los tiempos de ejecución, calcula el rendimiento en MFLOPS alcanzado en cada ejecución y las aceleraciones (speedups) respecto a la ejecución de este código con 1 procesador.

5. Planificación de iteraciones

La planificación de iteraciones puede controlarse mediante la orden schedule que se utiliza junto con la directiva omp for. Ejecuta el programa anterior con las siguientes estrategias de asignación de iteraciones a threads (sólo para 4 threads):

static.
static, con valores de chunk 1, 100 y 10000.
dynamic, con valores de chunk 1, 100 y 10000.
guided, con valores de chunk 1, 100 y 10000.

Compara los tiempos de ejecución obtenidos con las distintas estrategias de planificación y saca conclusiones de dicha comparación.

5. Multiplicación de matrices

En el directorio ´´´p5/matmul´´´ se proporciona un código para la multiplicación de matrices. Una primera versión secuencial, una segunda versión recursiva que particiona la multiplicación de matrices en bloques más pequeños, y una tercera versión paralela incompleta en la que faltan añadir las directivas OpenMP para su paralelización. Por favor, completa esta última versión. Ejercicio:

Estudia el impacto del tamaño de la matriz y número de threads en el rendimiento de la versión paralela.
Haz un estudio comparativo del rendimiento de las tres versiones: secuencial, recursivo y paralelo.

6. Optativo

(Optativo) Cálculo de aceleraciones en otros sistemas

Si tienes un procesador con varios núcleos (Dual-Core, Quad-Core, Hexa-Core . . . de Intel o AMD), puedes repetir la práctica con dicho sistema. Para ello necesitarás un compilador que soporte las directivas OpenMP (gcc, icc).
Si os apetece probar otras cargas de trabajo podéis probar con la benchmark suite Rodinia. Esta formada por varios programas de prueba que están implementados en distintos paradigmas de programación paralela, incluido OpenMP. Podéis utilizar alguno de estos progranas(, escalarlo para pilgor) y probar como se comporta. Os dejo algunos enlaces para poder acceder a Rodinia: página oficial de Kevin Skadron (http://lava.cs.virginia.edu/Rodinia/download_links.htm) ó repositorio en github (https://github.com/yuhc/gpu-rodinia).

Bibliografía https://gcc.gnu.org/onlinedocs/

Provide feedback

Saved searches

Use saved searches to filter your results more quickly