PDF de programación - Análisis de algoritmos paralelos

METODOLOGÍA DE LA PROGRAMACIÓN PARALELA

Análisis de algoritmos paralelos

La mayoría de los libros de la bibliografía, en particular:

REFERENCIAS

• Foster, cap 3
• Kumar, Grama, Gupta, Karypis, cap 4
• Wilkinson, Allen, cap 2.3 y 2.4
• Quinn

y, por supuesto, el de Introducción a la Programación
Paralela

1

Análisis de algoritmos paralelos

Los procesadores paralelos se usan para acelerar la
resolución de problemas de alto coste computacional.

La finalidad principal consiste en reducir el tiempo de
ejecución:

si el tiempo secuencial t(n)
se intentará que usando p procesadores el tiempo

se reduzca a t(n)/p.

Ver algunas medidas que nos dan idea de la "bondad"
de un algoritmo paralelo.

2

Tiempo secuencial

• El tiempo de ejecución de un programa secuencial
depende de:

tamaño de la entrada,
compilador,
máquina,
programador...,

si nos olvidamos de valores constantes dependientes del
sistema (por ejemplo el coste de una operación aritmética
en la máquina donde ejecutamos el programa) podemos
considerar el tiempo función del tamaño de la entrada:
t(n).
El tiempo desde que empieza la ejecución del programa
hasta que acaba.

3

Tiempo de ejecución paralelo

• En un programa paralelo la estimación del tiempo es
más compleja.
Además de los parámetros anteriores, depende de:

número de procesadores t(n,p),
de la manera en que están conectados entre sí
(topología) y con los módulos de memoria (memoria
compartida o distribuida)

• Es el tiempo transcurrido desde que empieza la
ejecución del primero de los procesadores hasta que
acaba el último de ellos.

4

Tiempo de ejecución paralelo

DIFICULTADES:

• No siempre es fácil determinar el orden en que los
procesadores empiezan y acaban.

• A lo largo de la ejecución de un programa paralelo hay
puntos de sincronización de los que no siempre podemos
determinar su duración al no saber en el orden en que
van a llegar los distintos procesos a estos puntos.

5

Tiempo de ejecución paralelo

• Esquema de programa paralelo:

(sincronización en memoria compartida)

Computación 1
Comunicación 1
Computación 2
Comunicación 2
...

t(n,p)=ta(n,p)+tc(n,p)

ta(n,p) : suma de los tiempos de las distintas partes de
computación
tc(n,p) : suma de los tiempos de las distintas partes de
comunicación

6

Tiempo de ejecución paralelo, ejemplo

• Programa paralelo en dos procesadores:

Computación 1 2

3

Comunicación 1

1

1

Computación 2 3

Comunicación 2

1

2

1

t(n,p)=ta(n,p)+tc(n,p)=7 (si se suman los tiempo por separado)

treal(n,p)=ta(n,p)+tc(n,p)+toverhead(n,p)=8

7

Tiempo de ejecución paralelo, ejemplo

2

1

3



t(n,p)=ta(n,p)+tc(n,p)=15

treal(n,p)=ta(n,p)+tc(n,p)-tsolapamiento(n,p)=14

8

Tiempo de ejecución

• Overhead debido a:

sincronización,
puesta en marcha de los procesos,
sobrecarga de la red de comunicación,
...

• Se suele considerar:

t(n,p)=ta(n,p)+tc(n,p)+to(n,p)-ts(n,p)

• Minimizar el tiempo de overhead.
• Maximizar el solapamiento.

9

Suma de n números

• Secuencial: t(n)=n-1

• Paralelo con n/2 procesadores, como mínimo t(n)/(n/2)=2

En cada Pi, i=0,1,...,n/2-1

inicio=2*i
desplazamiento=1
activo=true
para k=1,2,...,log n

si activo

a[inicio]=a[inicio]+a[inicio+desplazamiento]
desplazamiento=desplazamiento*2

finsi
si i mod desplazamiento <>0

activo=false

finsi
finpara

10

Suma de n números

• Pasos: log n

• Trabajo adicional (overhead):

Comprobación de si el procesador trabaja,
Uso de las variables,
Actualización de las variables.

• Con n=64

si cada paso secuencial y paralelo igual coste:

si cada paso secuencial coste 2 y paralelo coste 5:

t(n)@ 8*t(n,p)

t(n)@ 3.5*t(n,p)

• Y en memoria distribuida problema de acceso a los datos.

11

Suma de n números. En hipercubo

• Cada procesador tiene dos valores, a y b

En cada Pi, i=0,1,...,n/2-1

desplazamiento=1
activo=true
para k=1,2,...,log n-1

si activo

a=a+b
desplazamiento=desplazamiento*2
si i mod desplazamiento <>0

activo=false
enviar a a i-desplazamiento/2

en otro caso

recibir en b de i+desplazamiento/2

finsi

finsi
finpara
si i=0

a=a+b

finsi

12

Suma de n números. En hipercubo

P0
0 1

P2
4 5

P0
6 5

P2
22 13

P1
2 3

P3
6 7

P1
5 3

P3
13 7

P0
1 1

P2
9 5

P0
6 22

P2
22 13

P1
5 3

P3
13 7

P1
5 3

P3
13 7

P1
5 3

P3
13 7

P1
5 3

P3
13 7

P0
1 5

P2
9 13

P0
28 22

P2
22 13

13

Suma de n números. En hipercubo

• Pasos: log n

• Trabajo adicional (overhead):

Comprobación de si el procesador trabaja,
Uso de las variables,
Actualización de las variables,
Comprobación de enviar o recibir,
Envío o recepción.

• Con n=64

si cada paso secuencial coste 2 y paralelo coste 7:

t(n)@ 2,5*t(n,p)
si ts=2*tw y tw=2*tc:
t(n)@ 1,5*t(n,p)

si ts=10*tw y tw=10*tc:
t(n)@ 0,16*t(n,p)

14

Suma de n números. En malla

15

Suma de n números. En malla

• Si p=2n

2*(1+2+22+...+2n/2-1 )= 2n/2+1 comunicaciones

• Con n=64

si ts=2*tw y tw=2*tc:
t(n)@ 1,4*t(n,p)

si ts=10*tw y tw=10*tc:

t(n)@ 0,1*t(n,p)

16

Suma de n números. En anillo

• Si p=2n

1+2+22+...+2n-1 = 2n –1= p-1 comunicaciones

• Con n=64

si ts=2*tw y tw=2*tc:
t(n)@ 0,74*t(n,p)
si ts=10*tw y tw=10*tc:
t(n)@ 0,04*t(n,p)

17

Coste de comunicaciones

• Son de los siguientes órdenes:

Comunicación vecinos

hipercubo
malla
anillo
red

log p/2

2*√p
p-1

Comunicación todos



log p/2
log p/2
log p/2



p-1

• Además, la red puede estar congestionada al haber
muchos mensajes por haber muchos procesadores.
• Problemas:

Problema de poco coste y no apropiado para resolver en

paralelo,

granularidad pequeña, sólo como ayuda para diseñar un

programa pero no como programa final.

18

Causas de reducción de las prestaciones

• Contención de memoria:
En memoria compartida el acceso a datos comunes o que están en el
mismo bloque de memoria producirá contención.
Si los datos son de lectura puede no haber ese problema.
En el ejemplo los procesadores escriben en zonas distintas. No hay
problema de coherencia, pero puede haber de contención si hay datos
en los mismos bloques de memoria.

• Código secuencial:
Puede haber parte imposible de paralelizar, como puede ser la I/O.
En el ejemplo la inicialización de variables. Además, si los datos están
inicialmente en un procesador y hay que difundirlos el coste es lineal.

• Tiempo de creación de procesos:
El programa empieza a ejecutarse con un proceso que pone en marcha
los demás.
El coste de creación de los procesos puede ser importante si la
granularidad de éstos es pequeña.

19

Causas de reducción de las prestaciones

• Computación extra:
Si se obtiene programa paralelo a partir de secuencial, son necesarias
computaciones adicionales por:
uso de variables de control,
comprobación de identificadores de proceso,
cálculos adicionales o comunicaciones para obtener datos

calculados por otro procesador...

• Comunicaciones:
En memoria distribuida, es tiempo adicional al aritmético.
Pueden implicar trabajo de procesadores intermedios.

• Tiempo de sincronización:
Cuando un proceso tiene que esperar a que estén disponibles datos
procesados por otro.
Conlleva comunicaciones en memoria distribuida.

20

Causas de reducción de las prestaciones

• Desbalanceo de la carga:

El volumen total de la computación no se distribuye por igual entre
todos los procesadores:

en el ejemplo, en el primer paso trabajan todos pero en los pasos
siguientes va disminuyendo el número de procesadores que trabajan,

también es posible que partamos de una entrada que no se

puede balancear, por ejemplo si tenemos 12 datos para 8
procesadores,

o que el volumen de datos varíe a lo largo de la ejecución, con lo

que se necesitaría balanceo dinámico.

21

Granularidad de la computación

• Uso de muchos procesadores no es realista:
No dispondremos de tantos procesadores.
Aunque dispongamos de ellos hay caída de las prestaciones.

• La granularidad del sistema (sistema físico+algoritmo) indica la
cantidad de computación y datos asignados a cada procesador:
Grano fino: si a cada procesador se asignan pocos datos o se realiza poca
computación entre comunicaciones.
Grano grueso: si a cada procesador se asignan muchos datos o se realiza
mucha computación entre comunicaciones.

• Interesa programación paralela cuando el paralelismo es de
grano grueso. A partir de qué punto interesa depende de los costes
en el sistema (no será lo mismo en saturno que en marte+mercurio)

• En sistólicos y GPUs el paralelismo es de grano fino.



22

Suma de n números con p procesadores

En cada Pi, i=0,1,...,p-1

suma=0
para j=i*n/p, ...,(i+1)*n/p-1

suma=suma+a[j]

finpara
sincronización
a[i]=suma
inicio=i*2
desplazamiento=1
si i mod 2=0

activo=true

en otro caso

activo=false

finsi
para k=1,2,...,log p-1

si activo

a[inicio]=a[inicio]+a[inicio+desplazamiento]
desplazamiento=desplazamiento*2

finsi
si i mod desplazamiento <>0

activo=false

finsi

finpara

23

Suma, en memoria distribuida

suma=suma+a[j]

finpara

activo=true

activo=false

En cada Pi, i=0,1,...,p-1

suma=0
para j=0, ...,n/p-1
si i mod 2=0

recibir en b de i+1

en otro caso

enviar suma a i-1

finsi
desplazamiento=2
para k=1,2,...,log p-2

si activo

suma=suma+b
desplazamiento=desplazamiento*2
si i mod desplazamiento <>0

activo=false
enviar suma a i-desplazamiento/2

en otro caso

recibir en b de i+desplazamiento/2

finsi

finsi

finpara
si i=0

suma=suma+b

finsi

24

Suma de n números con p procesadores

• En memoria compartida todas las variables son locales
salvo el array a.
• En memoria distribuida la sincronización por el paso de
mensajes.
• El tamaño del problema (n) es múltiplo del número de
procesadores (p). Se puede generalizar fácilmente.
• t(n,p)=2*n/p*tc+6*(log p-1)*(ts+tw)

si p<<<n podemos tener en cuenta sólo los términos de