WIXLIB

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

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

El Modelo de Variables CompartidasDATOScabaDATOScba 2*ba 2*bsyncsyncc 2*aTAREAsc 2*aOPERACIONESLas operaciones se descomponen en tareas.Los datos son compartidos por todas las tareas.Se requieren primitivas de sincronización para: Señalización Acceso ExclusivoCEPBADAC

Expresión del Paralelismo en elModelo de Variables Compartidas Fork & JoinAForkBCDJoinECEPBAABCADEDAC

Expresión del Paralelismo en elModelo de Variables Compartidas DOALLADoall i 1, Na(i) : b(i)*c(i)enddoBAa(1)a(2)a(3)a(N)BCEPBADAC

Necesidad de Sincronización SeñalizaciónTarea A.x : f(a).Tarea B.y : f(x). Acceso exclusivovariable compartida {cont 0}Tarea. A.cont : cont 1.CEPBATarea. B.cont : cont 1.DAC

Primitivas de SincronizaciónSincronización mediante Loads y Stores convencionales Señalizaciónvariable compartida {s 0}Tarea A.x : f(a)s : 1.Tarea B.while s 0 doenddoy : f(x) Acceso exclusivovariables compartidas {cont 0, turno 0, procA fuera,procB fuera}Tarea ATarea BprocA: dentroif procB dentro thenif turno 1 thenprocA : fuerarepeat until turno 0procA : dentroendifrepeat until procB fueraendifprocB: dentroif procA dentro thenif turno 0 thenprocB : fuerarepeat until turno 1procB : dentroendifrepeat until procA fueraendifcont : cont 1cont : cont 1turno : 1procA: fueraturno : 0procB: fueraCEPBADAC

Primitivas de SincronizaciónPrimitivas de Bajo Nivel (con necesidad de soporte hardware)Usualmente implementadas en forma de instrucciónde lenguaje máquina. Test & SetSemánticaTest&Set (lock)tmp : locklock : 1Acceso Atómicoreturn tmpUso para Acceso Esclusivo{lock 0}.While (Test&Set (lock) 0)endwhile{acceso exclusivo}lock : 0CEPBADAC

Primitivas de SincronizaciónPrimitivas de Alto NivelImplementadas en base a primitivas de bajo nivelmás una cierta cantidad de software. SemáforosSemánticaWait (s)Signal (s)if s 0 thenif cola no vacía thenbloquea la tarea enuna colaelse s 0desbloquear el primierode la colaelse s 1Uso para Acceso Exclusivo{s 1}.Wait (s){acceso exclusivo}Signal (s)CEPBADAC

Primitivas de SincronizaciónPrimitivas de Alto Nivel BarrerasSemánticaBarrier (b)b : b 1if b Numproc thenbloquear tarea en la colaelsedesbloquear todas las tareas de la colab : 0Uso{b 0}While cond doleer información compartidacálculoactualización de la información compartidabarrier (b)endCEPBADAC

Primitivas de SincronizaciónPrimitivas de Alto Nivel MonitoresEjemploProducer-Consumer: monitorbeginbuffer está compartidois full es un booleanempty and full son semáforosprocedure produce (data)beginif (is full) thenwait (empty)endifbuffer : datais full : truesignal (full)endprocedure consume (data)beginif (not is full) thenwait (full)endifdata : bufferis full : falsesignal (empty)endinitializeis full : falseendCEPBADAC

Ejemplo de ProgramaciónCalcular un histogramas de notasAlgoritmo 1integer notas (N) SHARED (* notas son enteros entre 0 y 10 *)integer histo (0:10) SHAREDsemaphore s (0:10)integer idoall i 1,Nwait (s(notas(i)))histo (notas(i)) histo (notas (i)) 1signal (s(notas (i)))enddoCEPBADAC

Ejemplo de ProgramaciónCalcular un histogramas de notasAlgoritmo 2Se pretende reducir el coste de sincronizacióninteger notas (N) SHARED (* notas son enteros entre 0 y 10 *)integer histo (0:10) SHAREDsemaphore sinteger histo local (0:10)integer i, p, Numprocdoall p 0, Numproc-1do i p*N/Numproc 1, (p 1)*N/Numprochisto local (notas(i)) histo local (notas(i)) 1enddowait (s)do i 0, 10histo (i) histo (i) histo local (i)enddosignal (s)enddoCEPBADAC

El Modelo de Paso de MensajesDATOScabDATOSacba 2*ba 2*bsend(a)receive (a)c 2*aprocesoc 2*aOPERACIONESLas operaciones Y LOS DATOS se descomponen en procesos.Los procesos sólo tienen acceso directo a los datos privados(locales).Los datos no locales se acceden mediante intercambio de mensajesentre los procesos.CEPBADAC

Procesos y CanalesEn el modelo de paso de mensajes, un programa paralelo se vecomo un conjunto de procesos que se intercambian información através de canales.CEPBADAC

Primitivas para Paso de MensajesCanales Punto a PuntoPROCESO P2PROCESO P1send (dato, P2)orcanalcreceive (dato, P1)orsend (dato, c)receive (dato, c)Mailboxessend(dato, mbx)receive (dato, mbx)mbxCEPBADAC

Primitivas para Paso de MensajesSincronización en la comunicación Comunicación SíncronasendProceso 1bloqueadoProceso 2receiveComunicación más rápida porque no necesita buffering temporal. Comunicación AsíncronasendProceso 1Proceso 2bufferreceiveComunicación más lenta.Permite solapamiento cálculo/comunicación.CEPBADAC

Ejemplo de ProgramaciónCalcular el máximo de un vector de reales.Algoritmo 1Usa una línea de P procesos.Inicialmente, el proceso q almacena los elementos del (q-1)*N/P 1al q*N/P.Finalmente, el máximo es escrito por el proceso P.Vector11CEPBANqPDAC

Ejemplo de ProgramaciónAlgoritmo 1Código para el proceso qreal local data (N/P), maxloc, maxloc2maxloc - do j 1, N/Pif local data [j] maxlocthen maxloc local data [j]endifenddoif q 1 then send (maxloc, q 1)else if q Pthen receive (maxloc2, q-1)if maxloc2 maxlocthen maxloc maxloc2endifsend (maxloc, q 1)else receive (maxloc2, q-1)if maxloc2 maxlocthen maxloc maxloc2endifwrite (maxloc)endifendifCEPBADAC

Ejemplo de ProgramaciónAlgoritmo 2Vector11NqPEl máximo es escrito por el proceso P.CEPBADAC

Ejemplo de ProgramaciónAlgoritmo 2Código para el proceso qreal local data (N/P), maxloc, maxloc2maxloc - do j 1, N/Pif local data [j] maxlocthen maxloc local data [j]endifenddoif q P then send (maxloc, P)else do i 1, P-1receive (maxloc2, i)if maxloc2 maxlocthen maxloc maxloc2endifenddowrite (maxloc)endifEl código es más sencillo pero probablemente la topología decomunicación no coincide con la topología de interconexión(sonbrecarga debida al encaminamiento de las comunicaciones nolocales).CEPBADAC

¿Es más fácil programar en el modelo de VariablesCompartidas que en el de Paso de Mensajes?Una Versión para el Modelo de Variables Compartidasreal data (N) SHAREDinteger i,N,Bdoall i 1,N,Bdo j i, i B-1if data [i] data [j]then data [i] data [j]endifenddoenddodo i 1,N,Bif data [1] data [i]then data [1] data [i]endifenddowrite (data [1])CEPBADAC

Relación Organización-Modelo de ProgramaciónMODELO DE PROGRAMACIÓNVariables CompartidasORGANIZACIONCombinación naturalPoco escalableMemoriaCompartida Fácil de programarPaso de MensajesPoco escalableProgramación difícilProgramación fácilCombinación naturalProgramación difícilMemoria EscalableDistribuida Implementación difícil EscalableCEPBADAC

Paralelización AutomáticaObjetivosCODIGO SECUENCIALFORTRANCOMPILADORPARALELIZADORCODIGO PARALELOCEPBADAC

Paralelización AutomáticaParalelización para un modelo de Variables Compartidas.Técnicas BásicasIdentificación de dependencias entre sentenciasS1: A B CS2: D A ES3: A F DTipos de DependenciasS1DatosS2SalidaAntidependenciaS31S1DO i 1,NS1: X B(i)S2: C(i) X 1S3: A(i) 2*C(i-2)ENDDO10S22DistanciaS3CEPBADAC

Paralelización AutomáticaTécnicas BásicasEliminación de antidependencias y dependencias de salidaS1: A B CS2: D A ES3: A F DS1S1: A B CS2: D A ES3: AA F DS1DO i 1,NS1: X(i) B(i)S2: C(i) X (i) 1S3: A(i) 2*C(i-2)ENDDOS10S2S2S22S3CEPBAS3S3DAC

Paralelización AutomáticaTécnicas BásicasDistribución de BuclesDO i 1,NS1: X(i) B(i)S2: C(i) X (i) 1S3: A(i) 2*C(i-2)ENDDOS1DO i 1,NS1: X(i) B(i)S2: C(i) X (i) 1ENDDODOALL i 1,NS1: X(i) B(i)S2: C(i) X (i) 1ENDDODO i 1, NS3: A(i) 2*C(i-2)ENDDODOALL i 1, NS3: A(i) 2*C(i-2)ENDDOS10S20S22S3CEPBA2S3DAC

Paralelización AutomáticaTécnicas BásicasIntercambio de BuclesDO i 1,NDO j 1,ME(i,j) E(i-1,j)*B(i,j)ENDDOENDDODOALL j 1,MDO i 1,NE(i,j) E(i-1,j)*B(i,j)ENDDOENDDO1,0S10,1S1.CEPBADAC

Paralelización AutomáticaParalelización para un modelo de Paso de MensajesEl problema es mucho más complejo porque no basta con identificarsentencias que puedan ejecutarse en paralelo. También hay quetomar decisiones sobre la ubicación de datos.De momento no hay compiladores suficientemente satisfactorios.Actualmente se está trabajando en la linea de pedir ayuda alprogramador. El lenguaje ofrece unas directivas que permiten alprogramador especificar operaciones independientes y recomendardistribuciones de datos adecuadas para la aplicación. En estadirección se han propuesto lenguajes tales como Fortran D, VienaFortran o High Performance Fortran (HPF).CEPBADAC

High Performance Fortran (HPF)Fortran-90Anotaciones del UsuarioHPFCompiladorCódigo paraprocesadorvectorialCEPBACódigo paraSIMDCódigo paravariablescompartidasCódigo parapaso demensajesDAC

High Performance Fortran (HPF) Declaración de Arrays1) REALA(10);A(1), A(2), A(3), ., A(10)A( primero : último : salto )A(1 : 5: 2) A(1), A(3), A(5)A(10 : 1 : -3) A(10), A(7), A(4), A(1)2) REALM(4, 6)M(1 : 2 , :)M(1 : 4 : 2 , 5)CEPBAM(: , 2 : 6 : 2)M( 2 , :)DAC

High Performance Fortran (HPF) Operaciones con ArraysREAL A(5), B(5), V(10)V(1 : 5) A ** 2 B ** 2B A (5 : 1 : -1)WHERE (A(1:3) .NE. 0) V(1 : 3) B(1 : 3) / A(1 : 3)V(1 : 9) V (2 : 10)M (1 : 3, 3 : 6) M (2 : 4 , 1 : 4)CEPBADAC

High Performance Fortran (HPF) Funciones Intrínsecas DOT PRODUCT (Vector1, Vector2)a DOT PRODUCT ( B, C)B 123 CEPBAC 2 3 4a 20MATMUL (Matrix1, Matrix2)DAC

High Performance Fortran (HPF) Directivas para la distribución de adores(virtuales)CEPBADAC

High Performance Fortran (HPF) Directivas para la distribución de datos*AReal*8TEMPLATEALIGNALIGNALIGNDISTRIBUTE (BLOCK)CEPBA xytemplateA(N,N), x(N), y(N)t(N)A(i,j), t(i)y(i), t(i)x(*), t(i)t(N)DAC

High Performance Fortran (HPF) Directivas para la distribución de datos*AReal*8TEMPLATEALIGNALIGNALIGNDISTRIBUTE (CYCLIC)CEPBA xytemplateA(N,N), x(N), y(N)t(N)A(i,j), t(i)y(i), t(i)x(*), t(i)t(N)DAC

High Performance Fortran (HPF) Directivas para la distribución de BUTE (BLOCK,BLOCK)CEPBA xyA(N,N), x(N), y(N)t(N,N)A(i,j), t(i,j)y(i), t(i,*)x(j), t(*,j)t(N,N)DAC

High Performance Fortran (HPF) Primitivas para la expresión del paralelismoDO J 1, NDOALL I 1,NY(I) Y(I) A(I,J)*X(J)ENDDOENDDOCEPBADAC

Librerías Numéricas Paralelas Librerías Numéricas Las librerías numéricas son colecciones de rutinasque implementan operaciones habituales enaplicaciones científicas y de ingeniería. Las librerías pueden optimizarse para ressuelenofrecerunaimplementación eficiente de las librerías máspopulares en su computador. Las ventajas del uso de librerías son:Facilitan lanuméricas.construccióndeaplicacionesFacilitan la portabilidad de la aplicación sinsacrificar la eficiencia (si existe unaimplementación eficiente de la librería en elcomputador al que se transporta la aplicación).CEPBADAC

Librerías Numéricas Paralelas Algunas Librerías Numéricas BLAS (Basic Linear Algebra Subprograms)Es una colección de rutinas que implementanoperaciones básicas de álgebra lineal. Se organizanen tres niveles:BLAS 1: Son operaciones vector-vector.Producto InternoAXPYBLAS 2: Son operaciones matriz-vectorProducto de matrix por vectorActualizacion Rango-1BLAS 3: Son operaciones matriz-matrizProducto de matricesSistema triangular matricial de ecuacionesCEPBADAC

Librerías Numéricas Paralelas Algunas Librerías Numéricas LINPACKOperaciones de álgebra lineal de mayorcomplejidad que BLAS. De hecho, las rutinas deLINPACK usan rutinas BLAS1 y BLAS2.Descomposición LUDescomposición QR EISPACKOperaciones para el cálculo de valores y vectorespropiosCEPBADAC