DIRECTIVAS DE PARALELIZACION FORTRAN MP

Introducción

Este curso pretende dar una visión general sobre las directivas de paralelización Fortran MP, que permiten ejercer un mayor control sobre el código de programa del que tiene la paralelización automática. Esto da lugar a un mejor aprovechamiento de los recursos de la máquina Seymour, al especificarle como debe trabajar con cada región de nuestro programa. Las directivas Fortran MP se caracterizan por:

• Son faciles de usar, permitiendo una paralelización muy efectiva de bucles con la introducción de unos pocos comandos. Estos comandos no son compatibles con compiladores de otros vendedores, aunque si con la paralelización automática PFA.
• Se activan con la opción de compilación -mp. Esta opcion debe introducirse entre las que acompañan al comando f77 para permitir la paralelización del código.
• Se inician siempre con la clave c$. Por tanto, sin la opción -mp se leen como comentarios en el código, y el programa se ejecuta normalmente en serie. (Esto facilita la portabilidad del código, pudiendo ser ejecutado tanto en serie como en paralelo.)

Los contenidos del curso se muestran en el siguiente índice:

1. Directiva c$doacross.
   • Definición de variables.
   • Modificador if.
   • mp_schedtype y chunk.
2. Control del número de procesos.
3. Elementos de control del paralelismo.
4. Dependencia de datos.
5. Algunos consejos sobre como trabajar con MP.
6. Algunos ejemplos prácticos.
7. Documentación sobre Fortran MP.

Directiva c$doacross

c$doacrosses la directiva fundamental, que permite la paralelizacion de un bucle en distintos procesos. Su estructura general es:

c$doacross
c$&  share      (variable11,variable12,...),
c$&  local      (variable21,variable22,...),
c$&  lastlocal  (variable31,variable32,...),
c$&  reduction  (variable41,variable42,...),
c$&  if         (expresion logica),
c$&  mp_schedtype = type,
c$&  chunk        = chunksize
        

• c$& son extensiones de linea; continuan con la descripción de c$doacross y cualquier otra directiva iniciada en la linea superior.
• Las salidas y entradas de datos que puedan darse en el bucle afectado, deben ejecutarse en serie. Si no, el bucle no puede funcionar. Para ello se emplea una serie de directivas, con algunos ejemplos ilustrados más adelante.
• No esta permitido el anidamiento de c$doacross; al hacerlo el programa no puede funcionar.

A continuación se hace una explicación de los modificadores que pueden acompañar a este comando.

Definición de Variables

Se facilita el manejo de las variables optimizando el tiempo de ejecución.

• share: variables accesibles portodos los procesos.
• local: variables propias de cada región paralela, no accesibles por el resto.
• lastlocal: escalares de los que solo se salva el valor tras la última iteración.
• reduction: escalares empleadas en operaciones con eliminacion de otras variables:
  Ej: A = A + B; A = A*B; A = min(A,B); A = max(A,B) (En estos casos se puede definir c$doacross reduction(A); consultense los ejemplos).

Por defecto los índices de bucle son lastlocal; las variables nuevas dentro del bucle c$doacross son local; el resto de variables share. Nota importante: hay que tener en cuenta que estas variables se definen partiendo de los tres tipos principales de variables en serie de Fortran:

• Globales: corresponden a variables share.
• Automaticas (creadas en la llamada a los procesos en los que se encuentran, y destruidas a la salida de los mismos): corresponden a variables local.
• Estaticas (inicializadas a cero al inicio del programa, existen a lo largo de todo el mismo): no se permiten en paralelización MP. Para ello, no esta permitido emplear la opcion de compilacion -static (que convierte las variables locales en estáticas), y variables definidas con save y con data (también estáticas).

Un problema grave se da con las variables definidas dentro de un common, que por defecto son siempre de tipo share. Para definir un common con variables local son necesarias dos opciones de compilación, que indican al compilador que hacer con tales variables: -Wl,-Xlocal,***_, donde *** es el nombre del common con unicamente variables locales. Ejemplo: Suma de matrices

subroutine suma(A,B,C,M,N)
dimension A(M,N), B(M,N), C(M,N)
 
c$doacross local(i,j), share(A,B,C,M,N)   
   do 100 i = 1, M
     do 100 j = 1, N
       C(i,j) = A(i,j) + B(i,j)
100  continue

   return
   end

Modificador if

Solo se efectua la paralelizacion si se cumple la condicion impuesta. Se emplea:

• Para paralelizar solo cuando los bucles se hacen grandes:
  Ej:
  

  c$doacross local(i,j)
  c$& if(imax.gt.1000.and.jmax.gt.1000)
   do i = 1,imax
     do j = 1,jmax
       ...
     enddo
   enddo

• Para evitar dependencia de datos:
  Ej:
  

  c$doacross if(jmax.gt.imax), local(i)
   do i = 1, imax
     a(i) = b(i) + b(i+jmax)
   enddo

• Para equilibrar trabajo entre procesos:
  Ej:
  

  num = valor
  c$doacross local(i), if (num.eq.2)
     do i = 1, 2
       if(i.eq.1) call work1
       if(i.eq.2) call work2
     enddo

 
mp_schedtype y chunk.

mp_schedtype define el modo de distribución del trabajo en los distintos procesos. Junto a ella se define el valor de chunk (número de iteraciones de bucle incluidas en cada envio). Ambas permiten un mejor equilibrio de carga entre procesos, mejorando el rendimiento del programa (limitado por el proceso más lento). Las opciones de mp_schedtype son:

• simple (sin chunk): el total de iteraciones se divide entre el número de procesos: la primera división se envia al primer proceso, la segunda al segundo, ..., y la última al último proceso.
  Ej: Dadas 13 iteraciones en 4 procesos, los envios son: 1111 222 333 444.
• interleave (chunk=1 por defecto): cada envio (de tantas iteraciones como define chunk) es llevado a cada proceso de manera correlativa: el primero a la primera, el segundo a la segunda,...).
  Ej: Dadas 13 iteraciones en 4 procesos, con chunk=1, los envios son: 1234 1234 1234 1
• dynamic (chunk=1 por defecto): los envios se realizan a los procesos que van quedando libres.
• gss (sin chunk): modo dinámico, que se inicia con envios grandes y termina con envios de un tamaño mas pequeño. Es el mejor modo de conseguir que todos los procesos acaben al mismo tiempo.
• runtime: mp_schedtype y chunk quedan definidas por medio de variables de entorno: setenv MP_SCHEDTYPE type setenv CHUNK n .

Ejemplo del uso de mp_schedtype y chunk: conjunto de Mandelbrot.
El siguiente programa genera un conjunto de Mandelbrot de dimension 128x128, en el cada columna de puntos es determinada por un proceso distinto (paralelizacion de los bucles 'j'). Todas las variables se definen como locales, ya que son independientes en cada punto (i,j), excepto la variable data que es compartida en todos los casos.
Las iteraciones (i,j) tienen una duración bastante variable, ya que la condición de finalización del do while determina valores muy diferentes de 'k' dependiendo del punto al que se aplica.

integer i,j
  integer k, data(0:127,0:127)
  complex*8 c,m
c$doacross local(i,j,c,m,k), share(data),
c$& mp_schedtype = {simple | interleave | dynamic | gss}  
  do j = 0,127
   do i = 0,127
    c = cmplx (-2.+(4./127.)*j,-2.+(4./127.)*i)
    m = cmplx (0.,0.)
    k = 0           
    do while (abs(m).le.4..and.k.lt.5000)
     m = m**2 + c
     k = k + 1
    enddo
    data(i,j) = k
   enddo
  enddo
  stop
  end

La distribución de los valores de 'k' es bastante aleatoria. De ese modo, empleando mp_schedtype = simple o mp_schedtype = interleave el rendimiento conseguido puede no ser óptimo por una carga no equilibrada de los procesos. mp_schedtype = dynamic, y sobre todo mp_schedtype = gss reparten mejor el trabajo y posibilitan que todos los procesos puedan terminar a la vez, reduciendo el tiempo de ejecución.

Control del número de procesos.

El mejor modo de definir el número de procesos en que se debe ejecutar un programa es por medio de la variable de entorno:
%setenv MP_SET_NUMTHREADS N
Por defecto, esta es igual al número de CPUs en el sistema. 

Elementos de de control del paralelismo.

Existe una serie de funciones externas que, añadidas a nuestro codigo Fortran, nos permiten un mejor control sobre la ejecucion paralela de nuestro programa. Informacion completa sobre ellas se puede obtener a traves de las man pages, por medio de:

man mp
Lo que hacemos aqui es unicamente una enumeracion de las mas importantes:

1. Control de procesos:
   subroutine mp_set_numthreads()
   

   Determina el numero de procesos que deben ejecutar un programa.

   integer function mp_numthreads()
   

   Indica el numero de procesos que estan ejecutando un programa.

   integer function mp_my_threadnum()
   

   Indica que proceso esta determinando aquella parte de programa en la que se incluye.

   logical function mp_in_doacross_loop()
   

   Responde a la pregunta: ¿Estoy dentro de un bucle paralelo?



2. Sincronización de procesos:
   subroutine mp_setlock()
subroutine mp_unsetlock()
   

   La parte de codigo situada entre estas dos subrutinas se ejecuta una sola vez por cada proceso y de manera no simultanea (acceso limitado a un unico proceso a la vez).

   subroutine mp_barrier()
   

   Ningun proceso puede seguir adelante mientras no hayan llegado todos a este punto.



3. Bloqueo de procesos 'esclavos'.
   subroutine mp_block()
subroutine mp_unblock()
   

   Estas dos subrutinas rodean a una parte del código que no precisa de los procesos 'esclavos' para su ejecución. Entre ellas se dejan libres estos procesos, para que se puedan usar en otros trabajos.

   subroutine mp_blocktime(integer iters)
   

   Proceso automático de bloqueo o liberación de procesos esclavos, cuando estos dejan de formar parte del trabajo activo, y entran en el 'bucle de espera' un numero de veces definido por 'iters'.



4. Creación y destrucción de procesos.
   subroutine mp_create(integer num)
   

   Subrutina de creacion e inicializacion de procesos, de modo que el número total de procesos activos sea el indicado por 'num'.

   subroutine mp_destroy()
   

   Subrutina que elimina todos los procesos 'esclavos'.

   subroutine mp_setup()
   

   Subrutina que crea e inicializa procesos, en un número que si no se especifica en cualquier otra rutina de definición de procesos, adopta como valor el número total de CPUs de la maquina. No es necesaria; es llamada automaticamente en la entrada a la primera región paralela. 

    

   Dependencia de datos.

   Cuando se paralelice un bucle se debe uno asegurar de que no exista dependencia de datos (dependencia de los datos que se computan en una iteracion de los obtenidos en las iteraciones anteriores). Esto no se debe pasar por alto en paralelización MP, pues toda la responsabilidad de programación recae sobre el usuario (por lo que este debe estar siempre al tanto de no dar lugar a cálculos erroneos). En comparación, en paralelización automática PFA esto no es necesario, ya que el compilador se encarga de paralelizar solo los bucles en los que esta seguro de no encontrar dependencias de datos. Un modo fácil de saber si un bucle no tiene dependencia de datos, es que su ejecución sea reversible (la última iteración se pueda ejecutar la primera). Por otro lado, muchas veces es fácil eliminar la dependencia de datos en un bucle. Por ejemplo:

   integer a(20,20)
   k = 0
    do i = 1,20
     do j = 1,20
      k = k + 1
      a(i,j) = k
     enddo
    enddo

   Este bucle se puede paralelizar por medio de:

   integer a(20,20)
   c$doacross local(i,j) share(a)
     do i = 1,20
      do j = 1,20
       a(i,j) = 20*(i-1) + j
      enddo
     enddo

   En general, los casos mas dificiles de paralelizar son aquellos en los que los datos se van uniendo en una cadena de dependencias hasta el dato inicial. Sin embargo, en un bucle anidado estas dependencias pueden deberse a un unico indice, pudiendo paralelizar en otros indices del bucle. Por ejemplo:

   c$doacross local(i,j) share(imax,jmax,a,b)
     do j = 1,jmax
      a(1,j) = b(i)
      do i = 2,imax
       a(i,j) = a(i-1,j) + b(i)
      enddo
     enddo

   Finalmente, hay que tener especial cuidado con las llamadas a subrutinas externas desde un bucle que queramos paralelizar, ya que a veces las subrutinas hace llamadas a datos hallados en llamadas anteriores a la misma.  

 
  Algunos consejos sobre como trabajar con Fortran MP.

Una vez escrito el codigo de programa con todas las directivas MP, lo primero que hay que hacer es correrlo en serie para asegurarnos de que no hay errores de lenguaje y los resultados del programa son correctos. Para ello basta con compilar sin la opción -mp, con lo que 'olvida' las directivas de paralelización y crea un ejecutable que corre sin problemas sobre un procesador en serie.
Una vez que el programa en serie funciona sin errores, se debe hacer un estudio de dependencias de datos en los bucles, para saber cuando es posible paralelizar. Aqui nos puede ser muy util la paralelizacion automatica PFA; en los archivos de ayuda que genera el compilador (programa.w2f.f, programa.l), se nos indican los problemas por los que no se paralelizan muchos bucles, lo que nos puede ayudar a la hora de solventarlos. (Sin embargo hay que recordar que la paralelizacion automatica tiene un criterio muy conservador y que muchas veces se puede llegar mas lejos de los que esta indica; se recomienda consultar las preguntas más frecuentes para saber mas sobre paralelización automática).
Este proceso es iterativo: se debe hacer un estudio de cada bucle y comprobar con cada transformacion que los resultados son correctos. Este es un proceso bastante lento, por lo que se recomienda concentrarse en las partes del programa que tardan mas tiempo, y que en realidad son las unicas que nos van a permitir un mejor rendimiento del programa (en lo que se llama una paralelizacion de grano grueso). Por medio de la herramienta SpeedShop y sus diversas aplicaciones (ssusage, ssrun,...) podremos orientarnos sobre donde merece la pena paralelizar (consultense tambien las preguntas más frecuentes para saber más del tema).
Se debe tener tambien en cuenta que, a veces, los resultados erroneos son debidos a una mala definicion de las variables en nuestro programa (variables share que debian ser local, etc...). Esto se puede comprobar comparando la version serie del programa, con la version paralela corrida sobre un solo procesador: si los resultados no son iguales hay un problema de definción de variables. 

Algunos Ejemplos Prácticos.

1. Paralelizacion de bucles anidados:
   Paralelizacion de las unidades de trabajos mas largas, buscando el equilibrio entre procesos.
   

   c    Paralelizacion del bucle 
   c    interno (bucle mas largo).
   c    No vale la pena paralelizar 
   c    el bucle externo: la ganancia
   c    de tiempo se consigue con el 
   c    interno, y se pueden dar 
   c    problemas de equilibrio.
   
     do 10 j = 1,5
   c$doacross local(i),share(j)
      do 10 i = 1,1000
       b(i,j) = a(i,j)
   10  continue

2. Paralelizacion de operaciones con reduccion de variables:
   Una operacion de reduccion es del tipo:
   A = A+B, A = A*B, A = max(A,B), A = min(A,B).
   Como ya se indico, el modo mas simple de paralelizacion se limita a definir la variable A como reduction.
   

   c    Por medio de 'reduction', 
   c    uno se asegura de sumar una 
   c    vez todos los elementos de 'A' 
   c    a la variable 'red', aunque
   c    estemos trabajando en distintos 
   c    procesos.
   
     red = 0.0
   c$doacross local(i,j), 
   c$& share(A, imax, jmax), 
   c$& reduction(red)
     do j = 1,jmax
      do i = 1,imax
       red = red + A(i,j)
      enddo
     enddo

   
   
   Otro modo consiste en definir una variable auxiliar de reduccion para cada uno de los procesos en que estemos paralelizando. Este metodo esta especialmente recomendado en bucles grandes, ya que evita un grave problema de comparticion innecesaria o false sharing.
   Las variables reduction son en realidad un caso especial de variables share; se comparten en todos los procesos, y cada vez que son modificadas deben ser actualizadas en todos ellos, algo que no es necesario y que ralentiza enormemente el tiempo de ejecución.
   
   

   c En este programa se establece 
   c una variable de suma 'redj', que
   c es local en cada proceso y que 
   c no sufre 'false sharing'. Una vez 
   c obtenida la suma parcial en cada 
   c proceso, se obtiene la suma total, 
   c por medio de:
   c         c$call mp_setlock()
   c            red = red + redj
   c         c$call mp_setunlock()
   c Las funciones de sincronizacion 
   c 'mp_setlock' y 'mp_setunlock'
   c garantizan que a la sentencia de 
   c suma se accede una sola vez desde 
   c todos los procesos, contribuyendo 
   c cada uno con su suma parcial 'redj'.
   c ¡¡¡¡ Estas sentencias deben 
   c incluirse en el bucle que ha sido 
   c paralelizado, teniendo en cuenta 
   c que en cada proceso 'redj' es una 
   c variable distinta !!!!
   
     red = 0.0
   c$doacross local(i,j,redj)
     do j = 1,jmax
      redj = 0.0
      do i = 1,imax
       redj = redj + A(i,j)
      enddo
   c$call mp_setlock()
      red = red + redj
   c$call mp_setunlock()
     enddo 

3. Paralelización de bucles con entrada y salida de datos.
   c$doacross solo permiten entrada y salida de datos en serie. Para ello los comandos I/O deben estar dentro de llamadas a mp_setlock y mp_setunlock, que permiten ejecutarlos en serie.
   Empleando de nuevo el ejemplo anterior:
   

   red = 0.0
   c$doacross local(i,j,redj)
     do j = 1,3
      redj = 0.0
      do i = 1,3
       redj = redj + A(i,j)
      enddo
   c$call mp_setlock()
      write (*,*) redj
      red = red + redj
   c$call mp_setunlock()
     enddo 
     write(*,*) red

4. Paralelización de bucles con llamadas a funciones externas.
   as llamadas a funciones externas no plantean problemas a la hora de emplearlas en paralelo dentro de c$doacross.
   Uno debe preocuparse solo de definir correctamente de que tipo son las variables incluidas dentro de la funcion externa, para que estas sean interpretadas correctamente: (local, share...)
   La estructura general del bucle seria por tanto:
   

   c$doacross local(i)
     do i = i,imax
      call work(i)
     enddo
     ...
   
     subroutine work(i)
     ...
        

5. Problemas con un vector o matriz local.
   Un grave problema que presenta un programa Fortran es que el tamaño de un vector o matriz debe ser especificado de manera explicita en el código, al inicio del programa o subprograma en que se aplica. No se puede emplear para definir el tamaño una variable no especificada o un valor definido en un bloque common.
   Esto obliga a hacer vectores y matrices de gran tamaño, que en genera pueden quedar semivacios, pero que garantizan la validez del programa cuando el numero de elementos que se precisan se hace muy grande.
   

   c    Suma de vectores
   
     subroutine vector(A,B,C)
     dimension A(100), B(100), C(100)
   c$doacross local(i), share(A,B,C)
     do i = 1,100
      C(i) = A(i) + B(i)
     enddo
     return
     end 
   
   c    No es valido hacer lo mismo con 
   c    el siguiente codigo, cuando el 
   c    valor de 'n' no esta especificado 
   c    en el codigo.
   
     subroutine vector(A,B,C,n)
     dimension A(n), B(n), C(n)
   c$doacross local(i), share(A,B,C,n)
     do i = 1,n
      C(i) = A(i) + B(i)
     enddo
     return
     end