Modelos de Programación Paralela

Modelos de Programación Paralela
u Modelos de Programación para Multiprocesadores
u El Modelo de Variables Compartidas
u Expresión del Paralelismo en el Modelo de
Variables Compartidas
u Primitivas de Sincronización
u Ejemplo de Programación
u El Modelo de Paso de Mensajes
u Primitivas para Paso de Mensajes
u Ejemplo de Programación
u Paralelización Automática
u High PerformanceFortran
u Librerías Numéricas Paralelas

CEPBA

DAC

Modelos de Programación para Multiprocesadores
u Modelos de Programación Secuencial
 FORTRAN 77
 FORTRAN 77 + Librerías Paralelas
u Modelos de Programación Paralela
 Variables Compartidas
 Paso de Mensajes

CEPBA

DAC

El Modelo de Variables Compartidas
DATOS
c

a
b

a

DATOS
c

b
a=2*b
a=2*b
sync

sync
c=2*aTAREAs
c=2*a

OPERACIONES

Las operaciones se descomponen en tareas.
Los datos son compartidos por todas las tareas.
Se requieren primitivas de sincronización para:

 Señalización
 Acceso Exclusivo

CEPBA

DAC

Expresión del Paralelismo en el
Modelo de Variables Compartidas
u Fork & Join

A
Fork
B
C
D
Join
E

CEPBA

A

B

C
A

D

E

DAC

Expresióndel Paralelismo en el
Modelo de Variables Compartidas
u DOALL

A
Doall i=1, N
a(i) := b(i)*c(i)
enddo
B

A

a(1)

a(2)

a(3)

a(N)

B

CEPBA

DAC

Necesidad de Sincronización
u Señalización
Tarea A
.
.
x := f(a)
.
.
.

Tarea B
.
.
.
y := f(x)
.
.

u Acceso exclusivo
variable compartida {cont = 0}
Tarea A
.
.
cont := cont + 1
.
.
.

CEPBATarea B
.
.
cont := cont + 1
.
.
.

DAC

Primitivas de Sincronización
Sincronización mediante Loads y Stores convencionales

u Señalización
variable compartida {s= 0}
Tarea A
.
.
x := f(a)
s := 1
.

Tarea B
.
.
while s = 0 do
enddo
y := f(x)

u Acceso exclusivo
variables compartidas {cont = 0, turno = 0, procA = fuera,
procB = fuera}
Tarea A

Tarea B

procA:=dentro
if procB = dentro then
if turno = 1 then
procA := fuera
repeat until turno = 0
procA := dentro
endif
repeat until procB = fuera
endif

procB:= dentro
if procA = dentro then
if turno =0 then
procB := fuera
repeat until turno = 1
procB := dentro
endif
repeat until procA = fuera
endif

cont := cont + 1

cont := cont + 1

turno := 1
procA:= fuera

turno := 0
procB:=fuera

CEPBA

DAC

Primitivas de Sincronización
Primitivas de Bajo Nivel (con necesidad de soporte hardware)

Usualmente implementadas en forma de instrucción
de lenguaje máquina.
u Test & Set
Semántica
Test&Set (lock)
tmp := lock
lock :=1

Acceso Atómico

return tmp
Uso para Acceso Esclusivo
{lock = 0}
.
While (Test&Set (lock)≠0)
endwhile
{acceso exclusivo}
lock := 0CEPBA

DAC

Primitivas de Sincronización
Primitivas de Alto Nivel

Implementadas en base a primitivas de bajo nivel
más una cierta cantidad de software.
u Semáforos
Semántica
Wait (s)

Signal (s)

if s = 0 then

if cola no vacía then

bloquea la tarea en
una cola
else s = 0

desbloquear el primiero
de la cola
else s = 1

Uso para Acceso Exclusivo
{s = 1}
.
Wait (s){acceso exclusivo}
Signal (s)

CEPBA

DAC

Primitivas de Sincronización
Primitivas de Alto Nivel

u Barreras
Semántica
Barrier (b)
b := b+1
if b < Numproc then
bloquear tarea en la cola
else
desbloquear todas las tareas de la cola
b := 0
Uso
{b = 0}
While cond do
leer información compartida
cálculo
actualización de la información compartida
barrier (b)
end

CEPBA

DACPrimitivas de Sincronización
Primitivas de Alto Nivel

u Monitores
Ejemplo
Producer-Consumer: monitor
begin
buffer está compartido
is_full es un boolean
empty and full son semáforos
procedure produce (data)
begin
if (is_full) then
wait (empty)
endif
buffer := data
is_full := true
signal (full)
end
procedure consume (data)
begin
if (not is_full) then
wait (full)
endif...