Introduccion a la Programacion Paralela y sus taxonomias

Introduccion a la Programacion Paralela, las taxonomicas o clasficiaciones que existen dentro del mismo.

1. Programación Concurrente y Paralela
Otoño 2022
NRC: 60898
Introducción
Taxonomía
Paradigmas
Diseño y Comportamiento

2. Introducción:
Objetivodelparalelismo:Conseguirejecutarunprograma
inicialmentesecuencialenmenostiempoutilizandoparaello
variosprocesadores.
Idea:Dividirunproblemagrandeenvariosmáspequeñosy
repartirlosentrelosprocesadoresdisponibles.
Problemas:Estrategiadediseñoadecuada,elementosno
paralelizables,repartodetrabajoentrelosprocesadores.
Programación Paralela

3. Programación Paralela
Introducción:
Tiempo en
paralelo
Tiempo en
Secuencial
1 procesador
4 procesadores
tiempo
EsquemaIdealdelaparalelización
Suponiendoquetodoslosprocesadoresllevanacaboelmismo
tipoynúmerodeoperaciones,eltiempodeejecucióndeun
programaparalelosería:t/ncont=tiempodeejecución
secuencialyn=númerodeprocesadoresdisponibles

4. Introducción:
EsquemaREALdelaparalelización
Existendependenciassecuencialesentrelasvariablesdel
programa,portantolaunidaddeparalelizaciónsonlas
entidadesqueencapsulaninstruccionesynolasinstrucciones
porsímismas.
Tiempo en
paralelo
Tiempo en
Secuencial
1 procesador
4 procesadores
tiempo
Programación Paralela

5. Introducción:
FactorSpeedUpoAceleración:
•Esunamedidacomparativadelrendimientodeunsistema
multiprocesadorrespectodeunsistemamonoprocesador.
•Midequétanefectivaeslaparalelizacióndeunprogramafrente
asuversiónsecuencial.
Programación Paralela

6. Introducción:
FactorSpeedUpoAceleración:
•Tsec:Tiempodeejecucióndelprogramasecuencial
•Tpar:Tiempodeejecucióndelprogramaparalelo
Programación Paralela
SpeedUp=
T
sec
T
par

7. Introducción:
FactorSpeedUpoAceleración:
CONSIDERACIONES:
1.Sedebeutilizarelmejoralgoritmosecuencialconocido(del
problemaaresolver).
2.Deberáserportantoelalgoritmosecuencialmásrápidoque
puedaejecutarseenunsoloprocesador.
3.Elalgoritmoutilizadoparalaprogramaciónparalelasueleser
diferente.
Programación Paralela
SpeedUp=
T
sec
T
par

8. Introducción:
EjemplodeSpeedUp:
Suposiciones:
•Setienen4procesadoresparalaejecuciónparaleladela
aplicación
•Tpar=3hrs.
•Tsec=8hrs.
Programación Paralela
SpeedUp=
8hrs
3hrs
=
2.66
hrs
SpeedUpIdeal=4hrs

9. Introducción:
EjemplodeSpeedUp:
¿Quétanrealista(bueno)esesteSpeedUp?
Consideraciones:
1.Tiempoutilizadoenparalelizarelprograma
2.Calidaddelcódigofuente
3.Naturalezadelalgoritmoimplementado
4.Porcióndecódigointrínsecamentesecuencial(quétan
paralelizableeselalgoritmo)
SpeedUp=
8hrs
3hrs
=
2.66
hrs
Programación Paralela

10. Introducción:
EjemplodeSpeedUp:
¿Quétanrealista(bueno)esesteSpeedUp?
RESPUESTA:ElmáximospeedUpquesepuedealcanzarconla
implementaciónparaleladeundeterminadoalgoritmovienedada
porlallamadaLeydeAmdahl.
SpeedUp=
8hrs
3hrs
=
2.66
hrs
Programación Paralela

11. Ley de Amdahl:
EslacotasuperioralSpeedUpquecomomáximopuedealcanzar
unprogramaejecutándoseenparalelo,suponiendoqueentodo
programahayunafraccióndecódigoquenosepuedeparalelizar
Programación Paralela
Seaf=fraccióndelcómputoquenopuedeserdivididaentareas
concurrentes
Seap=elnúmerodeprocesadores
S(p)=elfactordespeedUpmáximodadoporlaleydeAmdahly
sedefinecomo:

12. Ley de Amdahl:
Programación Paralela
S(p)=
p
1+(p-1)f
f+[(1-f)/p]
S(p)=
1

13. Ley de Amdahl:
Ejemplo:Setieneunprogramaconunafraccióndecódigo
paraleloequivalenteaun75%ylaaplicaciónseejecutautilizando
4procesadores
Seaf=0.25
Seap=4
Programación Paralela
S(4)=
4
1+(4-1)0.25
= 2.28

14. Ley de Amdahl:
Ejemplo:Setieneunprogramaconunafraccióndecódigo
paraleloequivalenteaun75%ylaaplicaciónseejecutautilizando
4procesadores
Seaf=0.25
Seap=4
Programación Paralela
= 2.28
0.25+[(1-0.25)/4]
S(4)=
1
SpeedUp<= S(p)

15. Ley de Amdahl:
Programación ParalelaLey de Amdahl
0
2
4
6
8
10
12
14
16
18
20
4 8 12 16 20
Número de procesadores P
Factor de cota superior de
SpeedUp S(P)
f=0
f=0.05
f=0.10
f=0.20

16. Ley de Amdahl:
LacotasuperiordelSpeedUpmejoraamedidaqueseaumentael
númerodeprocesadores
Conunnúmeroinfinitodeprocesadores,elmáximospeedUpque
sepuedealcanzarestalimitadopor1/f
Programación Paralela
limS(p)
p →
=
1
f

17. Ciclos por instrucción (CPI):
Esunamedidautilizadaparareflejarlacalidaddeusodel
procesadorporpartedeunprograma
Programación Paralela
# instrucciones
CPI=
# ciclos
Siporcadacicloseejecutaunainstrucción,elCPI=1locualse
considerabueno
Losprocesadoressuperescalaresejecutanmásdeunainstrucción
deunprogramaporciclo,esdecir,0<CPI<=1

18. TAXONOMÍA:
Losmultiprocesadoresseclasificandeformagenéricaen:
-MultiprocesadoresdeMemoriaCompartida
-MultiprocesadoresdeMemoriaDistribuida
-MultiprocesadoresdeMemoriaCompartidaDistribuida
Programación Paralela

19. CPU Memoria CPU Memoria
RED DE INTERCONEXION
CPU Memoria CPU Memoria
TAXONOMÍA:
MultiprocesadoresdeMemoriaDistribuida:Computadoradonde
lamemoriadelsistemaestadistribuidaentretodoslos
procesadoresdelsistema,usandodelpasodemensajesparala
comunicaciónentrelosprocesadores
Programación Paralela

20. Memoria
CPU CPU
RED DE INTERCONEXION
CPU CPU
Mem
CPU CPU
RED DE INTERCONEXION
CPU CPU
Mem Mem Mem
Fig. I.5. (a) Modelo NUMA Fig. I.5. (b) Modelo UMA
TAXONOMÍA:
MultiprocesadoresdeMemoriaCompartida:Multicomputadoras
dondetodoslosprocesadoresaccedenatodalamemoria.Silos
procesadoresaccedenalamemoriaenuntiempouniforme,
entoncessetieneelmodeloNUMA,delocontrario,estaremos
conunmodeloUMA.
Programación Paralela

21. Memoria
Switch local
I/O
CPU CPU
Nodo
Memoria
Switch local
I/O
CPU CPU
Nodo
RED DE INTERCONEXION GLOBAL
TAXONOMÍA:
MultiprocesadoresdeMemoriaCompartidaDistribuida:
Computadoradondelamemoriaestafísicamenterepartidaentre
losnodosdelsistemacompuestopor2procesadoresc/uysolo
hayunespaciodedireccionesytodoslosprocesadoresaccedena
todalamemoria.
Programación Paralela

22. Clasificaciónde Michael Flynn:
Programación Paralela
MIMD
SIMD
Mybrid
MISD
Multiprocesadores
Procesadores de Arrays
Procesadores de Vector Pipeline
Procesadores de Vector Pipeline
Arrays Sistólicos
Máquinas SIMD-MIMD
Máquinas MIMD-SIMD
Multicomputadores
Máquinas de flujos de datos

23. Arquitectura SISD(Simple InstructionStream, Simple Data
Stream):
Programación Paralela
Procesador
Instrucciones
Datosde
Entrada
Datosde
Salida
La ArquitecturaSISD

24. Arquitectura SISD(Simple InstructionStream, Simple Data
Stream):
Programación Paralela
1.SebasaenelmodelodeVon-Neumman
2.CuentaconunCPUqueejecutaunainstrucciónalaveze
instancíaunitemdedatosalavez
3.Utilizaunregistrosimplellamadocontadordeprograma(CP)
parallevarelconteoserialdelasinstrucciones
4.Lasinstruccionessonejecutadasatravésdelciclo-fetchdela
máquinaenordenserial

25. Arquitectura SISD(Simple InstructionStream, Simple Data
Stream):
Programación Paralela

26. Arquitectura SIMD(Simple InstructionStream, MultipleData
Stream):
Programación Paralela
Flujo de
Instrucción
Procesador
A
Flujo de
Entrada de
Datos A
Flujo de Salida de
Datos A
Flujo de
Entrada de
Datos B
Flujo de
Entrada de
Datos C
Procesador
B
Procesador
C
Flujo de Salida de
Datos B
Flujo de Salida de
Datos C
La Arquitectura SIMD

27. Arquitectura SIMD(Simple InstructionStream, MultipleData
Stream):
Programación Paralela
1.TodoslosCPUsrecibenlamismainstrucciónaejecutarpor
partedelaCUperooperancondistintosconjuntosdedatos.
2.Distribuyenelprocesamientosobrehardwaregrande
3.Operanconcurrentementeconmuchosdatosdistintos
4.Realizanelmismocálculoentodosloselementosdedatos

28. Arquitectura SIMD:
Programación Paralela
MasParMP-1ILLIAC-IV

29. Arquitectura MISD(MultipleInstructionStream, SingleData
Stream):
Programación Paralela
Flujo de
Instrucciones A
Procesador
A
Flujo de
Entrada de
Datos
Procesador
B
Procesador
C
Flujo de
Salida de
Datos B
La Arquitectura MISD
Flujo de
Instrucciones B
Flujo de
Instrucciones C

30. Arquitectura MISD(MultipleInstructionStream, SingleData
Stream):
Programación Paralela
1.Arquitecturadecomputadoraqueejecutavariosprogramas
distintosparaelmismoconjuntodedatos
2.Sepuedentenercomputadorasquerequierendedistintas
unidadesdeprocesamientoquerecibendistintasinstrucciones
paraoperarsobrelosmismosdatos
3.Sepuedentenercomputadorastalesqueelflujodedatos
circulasobreunaseriedeelementosdeprocesamiento
4.Ejemplodeellosonlosarraysistólicosopipeline(cauces)

31. Arquitectura MISD:
Programación Paralela
NECNehalemCluster

32. Arquitectura MIMD(MultipleInstructionStream, MultipleData
Stream):
Programación Paralela
Flujo de
Instrucciones A
Procesador
A
Flujo de
Entrada de
Datos A
Procesador
B
Procesador
C
Flujo de
Salida de
Datos B
La Arquitectura MIMD
Flujo de
Instrucciones B
Flujo de
Instrucciones C
Flujo de
Entrada de
Datos B
Flujo de
Entrada de
Datos C
Flujo de
Salida de
Datos A
Flujo de
Salida de
Datos C

33. Arquitectura MIMD(MultipleInstructionStream, MultipleData
Stream):
Programación Paralela
1.Sonsistemasmultiprocesadoresomulticomputadorasdonde
cadaprocesadortienesuunidaddecontrolyejecutasu
propioprograma
2.Distribuyenelprocesamientosobreprocesadores
independientes
3.Compartenflujosorecursosentreprocesadores
4.Sonarquitecturasutilizadasparaparalelismodegranofinoy
obtenerasímáseficiencia

34. Arquitectura MIMD:
Programación Paralela

35. Memoria
del sistema
A
Procesador
A
Procesador
B
Procesador
C
Bus de
memoria
Bus de
memoria
Bus de
memoria
MemoriadistribuidaenmáquinasMIMD
Memoria
del sistema
B
Memoria
del sistema
C
Arquitectura MIMD:
Programación Paralela

36. Sistema de Memoria Global
Procesador
A
Procesador
B
Procesador
C
Bus de
memoria
Bus de
memoria
Bus de
memoria
MemoriacompartidaenmáquinasMIMD
Arquitectura MIMD:
Programación Paralela

37. Programación Paralela
Diseño y Comportamiento:
AlgoritmosParalelos:Describencomopuederesolverseun
problemapensandoenunadeterminadaarquitecturaparalela,
medianteladivisióndelproblemaensubproblemas,comunicando
losprocesadoresydespuésuniendolassolucionesparcialespara
obtenerlasoluciónfinalysuelenbasarseenelconceptode
paradigma.
Paradigma:Esunaclasedealgoritmosqueresuelvendiferentes
problemasquetienenlamismaestructuradecontrol.
-Porejemplo:DivideyVencerás,MultiplicacióndeTuplas,
ProgramaciónDinámica,RamificaciónyPoda,etc.
-CaendentrodeláreadeTeoríadealgoritmosparalelos

38. Programación Paralela
Patrones de Comunicación Paralela:
LosParadigmasdefinenunametodologíadeprogramacióndentro
delaCienciaComputacionalaplicandounprocesodederivación
informalparasuprogramaciónendondeseidentificaunpatrón
decomunicaciónparalelaparalainteracciónentrelosprocesos.
Patronesdecomunicaciónparalela:
-Farmsogranjas
-PipelinesoCauces
-Treesoárboles
-Cubos
-Hipercubos
-Matricesomallas

39. Programación Paralela
Diseño y Comportamiento:
FarmsoGranjas:Formadasde
unconjuntodeprocesos
trabajadoresyunproceso
controlador.Lostrabajadores
seejecutanenparalelohasta
alcanzarunobjetivocomúny
elcontroladordistribuyeel
trabajoycontrolaelprogreso
delcómputoglobal.
Proceso
Trabajador
Farmcon un proceso controlador y 5 procesos trabajadores
Proceso
Trabajador
Proceso
Trabajador
Proceso
Trabajador
Proceso
Trabajador
Proceso
Controlador
Patronesdecomunicaciónparalela:

40. Programación Paralela
Diseño y Comportamiento:
PipelinesoCauces:Estacompuestoporunconjuntodeprocesos(llamados
stages,etapasoestados)conectados,unodetrásdeotroydondela
informaciónsigueunflujoocaucedeunoaotrostage
Patronesdecomunicaciónparalela:
P0 P1 P2

41. Programación Paralela
Diseño y Comportamiento:
TreesoÁrboles:Hace
quelainformaciónfluya
desdeelprocesoraíz
hacialosprocesoshojas
oviceversa,ejecutándose
enparalelolosnodosque
seencuentranenel
mismoniveldelárbol
Patronesdecomunicaciónparalela:
P0
P1 P2
P3 P4 P5 P6
P7 P8 P9 P1
0
P11 P12 P13 P14

42. Programación Paralela
Diseño y Comportamiento:
Cubos o Hipercubos:
Conjuntodeprocesos
interconectadosentresí
formandouncubon-
dimensionalporejemplo,dos
cubos,cadaunocon8nodos
dondecadanodosesta
formadopordosprocesos,
conectadosasuvezconotros
nodosformandoaristas.
Patronesdecomunicaciónparalela:

43. Programación Paralela
Diseño y Comportamiento:
MatricesoMallas:En
unamallacadaproceso
estaconectadoconsus
vecinosy todos
contribuyenentresípara
resolverencomúnun
problema,ejecutándose
enparalelo.
Patronesdecomunicaciónparalela:

44. Programación Paralela
Diseño y Comportamiento:
Metodologíaparadefinirunparadigma:
1.Identificarelcomportamientoparalelo(patróndecomunicación
entreprocesos)delaaplicaciónendesarrollo.
2.Elaborarunbosquejográficodesurepresentación.
3.Realizarunadefiniciónsintácticay/osemántica
4.Traducirdichadefiniciónaunprogramaenelentornode
programaciónmásadecuadoparasuimplementación
5.Verificarquelasemánticaresultantesealacorrectaprobandocon
variosejemplosdistintosdemostrandosugenericidad
6.Observarelrendimientodelasaplicaciones

45. Programación Paralela
Diseño y Comportamiento:
Metodologíaparadefinirunparadigma: