PDF de programación - Parte II. Introducción al Paralelismo: Herramienta - Técnicas de Computación Científica

Técnicas de Computación Científica

Parte II. 

Introducción al Paralelismo: Herramientas.

      FIM ­  2008/9

Vicente Martín
        v0.2a

Herramientas de Programación Paralela
● Como muestra de las más significativas, por 

uso/estandarización/filosofía nos centraremos en:
– High Performance Fortran: HPF
– Message Passing Interface: MPI
– Open Multi Processing: OpenMP
– Unified Parallel C: UPC

● Antes de tratar cada uno con más detalle, veremos 

sus ideas básicas y algún ejemplo simple. 

Ideas Básicas.

● HPF: Funciona como directivas que pueden ser 

condicionalmente compiladas, algunos intrínsecos y atributos 
que regulan el tipo de ejecución/alcance de datos de una 
subrutina. Pretende ignorar si la máquina sobre la que funciona 
es un multicomputador o un multiprocesador. 

● OpenMP: Directivas condicionalmente compiladas y variables 

de entorno. Basado en hilos de ejecución. Destinado a 
Multiprocesadores. Paralelización “incremental”.

● MPI: Paso de mensajes explícito a base de llamdas a funciones 

de librería. Destinado a multicomputadores. Sobrecarga 
importante para el programador. En general, el programa debe 
ser diseñado desde el principio pensando en MPI. 

Ideas Básicas.

● UPC: Extensiónn de C (nuevas palabras reservadas, tipos, 
variables de entorno, funciones de librería ). Modelo DSM 
(Distributed Shared Memory).  Pensado para hacer uso eficiente 
de la localidad de datos en máquinas NUMA. Basado en hilos 
de ejecución y en una memoria global (además de la privada de 
cada hilo) en donde se puede establecer una relación de afinidad 
de una sección con un determinado hilo para mantener la 
localidad de referencias  entre los datos necesarios y el hilo que 
los procesa.

Ejemplos.

● Para obtener una idea de los tres paradigmas, de 

su filosofía, complejidad y rendimiento, los 
siguientes programas calculan el valor de la 
integral por el método de los trapecios:

1

=∫0

4
1x2 dx

– En el caso de HPF se dan varias declaraciones de la 

función, todas correctas, para estudiar el distinto 
rendimiento de cada una (en el ejemplo sólo se usa 
una, inlined)

OMP

 Program Trapecios
 
! El metodo de los trapecios en version Open MP

  Integer(Kind(1))   :: n,i
  Real( Kind(1.D0))   :: w, x, suma, pi, a
  Integer :: InitialClock, FinalClock, TicksPerSecond

  Print *,' Numero de intervalos='
  Read *,n

  w = 1.0d0/n
  suma = 0.0d0

 Call System_Clock(InitialClock)

!$OMP  PARALLEL DO PRIVATE(x), SHARED(w), REDUCTION(+: suma)

 Do i=1, n

   x= w * (i­0.5D0)
   suma = suma + f(x)
 End Do

 Call System_Clock(FinalClock,TicksPerSecond)

 Print *,' Segundos :', Float(FinalClock­InitialClock)/(Float(TicksPerSecond))
 Pi = w * suma
 Print *,' Pi= ' , Pi

End

 Program Trapecios
! El metodo de los trapecios en version HPF
  Integer(Kind(1))   :: n,i
  Real( Kind(1.D0))   :: w, x, suma, pi, a
  Real(Kind(1.D0)), Allocatable :: Puntos(:), funcion(:)     
  Integer  :: InitialClock, FinalClock, TicksPerSecond

!HPF$ PROCESSORS P(4)
!HPF$ DISTRIBUTE (BLOCK) ONTO P :: Puntos , Funcion           

  Print *,' Numero de intervalos='
  Read *,n
  Allocate (Puntos(n))
  Allocate (funcion(n))

  w = 1.0d0/n
  suma = 0.0d0
  Print *,' *** FORALL + Intrinseco SUM'

 Call SYSTEM_CLOCK(InitialClock)
 
!HPF$ INDEPENDENT 
 ForAll ( i=1:n )  funcion(i) = 4.0D0/(1.0D0+ (w * (i­0.5D0))**2)
 suma = SUM(funcion)

 Call SYSTEM_CLOCK(FinalClock)

 Print *,' Segundos :',  &
Float(FinalClock­InitialClock)/Float(TicksPerSecond)
 Pi = w * suma
 Print *,' Pi= ' , Pi                  

HPF

CONTAINS
    
! Funcion pura. Recibe UN ESCALAR y 
! devuelve UN ESCALAR.

 PURE REAL(Kind(1.D0)) FUNCTION f(a)

 Real(Kind(1.D0)), INTENT(IN) :: a

 f = 4.0D0/(1.D0 + a*a)

 End FUNCTION f       

! Funcion pura. Recibe UN VECTOR y devuelve 
! otro VECTOR.

 PURE Function fv(a)

 Real(Kind(1.D0)), Dimension(:), Intent(IN) :: a
 Real(Kind(1.d0)),Dimension(Size(a)) :: fv

 fv = 4.0D0/(1.D0 + a*a)

 End Function fv 
 
 End PROGRAM Trapecios

      program main
      include "mpif.h"
      double precision  PI25DT
      parameter   (PI25DT = 3.141592653589793238462643d0)
      double precision  mypi, pi, h, sum, x, f, a
      double precision starttime, endtime
      integer n, myid, numprocs, i, ierr
c                                 function to integrate
      f(a) = 4.d0 / (1.d0 + a*a)

      call MPI_INIT(ierr)
      call MPI_COMM_RANK(MPI_COMM_WORLD, myid, ierr)
      call MPI_COMM_SIZE(MPI_COMM_WORLD, numprocs, ierr)

 10   if ( myid .eq. 0 ) then
         print *, 'Enter the number of intervals: (0 quits) '
         read(*,*) n
      endif
c                                 broadcast n
      starttime = MPI_WTIME()
      call MPI_BCAST(n,1,MPI_INTEGER,0,
  &                                   MPI_COMM_WORLD,ierr)
c                                 check for quit signal
      if ( n .le. 0 ) goto 30
c                                 calculate the interval size
      h = 1.0d0/n
      sum  = 0.0d0

MPI

      do 20 i = myid+1, n, numprocs
         x = h * (dble(i) ­ 0.5d0)
         sum = sum + f(x)
 20   continue
      mypi = h * sum
c                                 collect all the partial sums
      call MPI_REDUCE(mypi,pi,1,MPI_DOUBLE_PRECISION,
     &                          MPI_SUM,0, MPI_COMM_WORLD,ierr)
c                                 node 0 prints the answer.
      endtime = MPI_WTIME()
      if (myid .eq. 0) then
         print *, 'pi is ', pi, ' Error is', abs(pi ­ PI25DT)
         print *, 'time is ', endtime­starttime, ' seconds'
      endif
      goto 10
 30   call MPI_FINALIZE(ierr)
      stop
      end

/*Copyright (C) 2000 Chen Jianxun, Sebastien Chauvin, Tarek El­Ghazawi */
#include <upc.h>
#include <upc_relaxed.h>  /*modo por omision, no es necesario ponerlo*/ 
#include <math.h>

UPC

#define N 32767 

#define f(x) 1/(1+x*x)

upc_lock_t l;
shared float pi;

void main(void)
{
  float local_pi=0.0;
  int i;

  upc_forall(i=0; i<N; i++; i%THREADS)
    local_pi+=(float)f((0.5+i)/N);

  local_pi*=(float)4.0/N;

  upc_lock(&l);
  pi+=local_pi;
  upc_unlock(&l);

  upc_barrier 1;  // Ensure all is done

  if (MYTHREAD==0) printf("PI=%10.9f\n",pi);
}

HPF

● Lenguaje de programación completo para programación 

tipo paralelismo de datos (modelo SPMD). 
● Objetivos: Buen rendimiento, portabilidad, 

compatibilidad con el lenguaje base (f95). Tanto en 
máquinas de memoria compartida como distribuida.

● Entra en forma de directivas (salvo intrínsecos nuevos) 

en el programa fuente.

● Especificación 1.0 en 1993. La 2.0 en 1997. La mayoría 

de implementaciones son subset de 1.1

● Proceso de compilación muy complejo, rendimiento 

difícil de prever. Futuro incierto.

Introducción a HPF

● El modelo básico de funcionamiento de HPF se 

conoce como SPMD (Single Program Multiple Data). 
Un programa único se ejecuta simultáneamente en una 
serie de procesadores actuando sobre conjuntos de 
datos distintos.

● Por ello, las principales directivas de HPF (marcadas 

con !HPF$) se ocupan de distribuir conjuntos de 
datos alineados (con una relación de proximidad de 
uso) entre si  sobre arrays regulares de 
procesadores que, en principio, son virtuales.

Modelo de asignación de datos a procesadores físicos.

Directivas: Distribución de Datos

● ALIGN: Especifica 
elementos que, si es 
posible, serán 
asignados al mismo 
procesador, de modo 
que operaciones entre 
elementos alineados 
mantendrán localidad 
de referencias..
– Las dimensiones “*” 
no se distribuyen: se 
colapsan

 Dbpp: Foster

Directivas: Creación de Disposiciones de 

Procesadores

● Para crear las disposiciones regulares (cartesianas) 

de procesadores abstractos sobre las que se 
distribuirán los datos alineados.

● Directiva PROCESSORS:

– !HPF$ processors linea(4)
– !HPF$ processors red(2,2)

● La primera crea un vector  con cuatro procesadores. 

La segunda, una matriz de 2x2 procesadores.

Directivas: Creación de Disposiciones de 

Procesadores

●  Se puede averiguar el número de procesadores 

disponibles y su forma usando los intrínsecos:
– NUMBER_OF_PROCESSORS(): Se puede utilizar dentro de 

una línea iniciada con !HPF$ como en 

● !HPF$ Processors Linea(NUMBER_OF_PROCESSORS())

– PROCESSORS_SHAPE(): Si no aparece una directiva 

PROCESSORS, el sistema usará una por omisión, que no tiene 
por qué ser óptima. Si el HW sobre el que funciona es un 
multiprocesador UMA, la forma de distribución de 
procesadores no tendrá mucho impacto.

Directivas: Distribución de Datos

● Sobre las disposiciones de procesadores se distribuyen 

los datos alineados usando DISTRIBUTE.

● Admite como parámetros BLOCK, CYCLIC o * (que 
expresa que no habrá distribución) BLOCK y CYCLIC 
admiten un argumento indicando el tamaño de bloque o 
el ciclo.

● Las únicas tablas distribuibles son los “objetivos de 

alineamiento final”: Referencias para los alineamientos 
de las demás tablas y que ellas mismas no están 
alineadas con ninguna.

Ejemplo de Directivas Básicas.

● Imaginemos que hemos definido las disposiciones linea(4) y red(2,2)  como
  en los ejemplos anteriores y que tenemos una matriz M de 8x8.

Efecto en las Comunicaciones.
● Estas tres directivas especifican cuales serán las 

comunicaciones en una operación dada.

● Ejemplo (del estándar), si tenemos el siguiente trozo de 

código:

Real A(1000),B(1000),C(1000),X(500),Y(0:501)
Integer INX(1000)

!HPF$   Processors PROCS(10)
!HPF$   DISTRIBUTE A(BLOCK) ONTO PROCS
!HPF$   DISTRIBUTE B(BLOCK) ONTO PROCS
!HPF$   DISTRIBUTE INX(BLOCK) ONTO PROCS
!HPF$   DISTRIBUTE C(CYCLIC) ONTO PROCS
!HPF$   ALIGN x(I) WITH Y(I­1)

A(I) = B(I)                      ! (1)
X(I) = Y(I­1)                    ! (2)
A(I) = C(I)                      ! (3)
A(I) = A(I­1) + A(I) + A(I+1)    ! (4)
C(I) = C(I­1) + C(I) + C(I+1)    ! (5)
X(I) = Y(I)                      ! (6)
A(I) = A(INX(I)) + B(INX(I))     ! (7)

● A, B, INX se distribuye en bloque sobre PROCS:  
   A(1:100) en PROCS(1); A(101:200) en 

PROCS(2) etc.

● C se distrib