Presentación - Lenguajes Paralelos

DefinicionVentajas y Desventajas

Analisis de DependenciaCaso de Estudio 1: Chapel

Caso de Estudio 2: X10Otros lenguajes paralelos

Lenguajes Paralelos

Nestor A. Rojas E.

Facultad Experimental de Ciencias y TecnologıaUniversidad de Carabobo

8 de julio de 2013

Nestor A. Rojas E. Lenguajes Paralelos




Contenido I

1 DefinicionConceptoPequena historia

2 Ventajas y DesventajasVentajasDesventajas

3 Analisis de DependenciaAnalisis de DependenciaCondiciones de Bernstein

4 Caso de Estudio 1: ChapelChapelRevisando Chapel

Tipos de DatosEstructuras de control





Contenido II

Estructuras de control paralelas

Algunos Ejemplos

5 Caso de Estudio 2: X10X10Revisando X10

Tipos de Datos y ClasesLugares y actividadesRelojesArreglos distribuidos

Un Ejemplo

6 Otros lenguajes paralelos





ConceptoPequena historia

Lenguajes Paralelos

Son aquellos lenguajes de programacion especialmente disenadospara la programacion en paralelo, generalmente trabajan conmemoria compartida. Proveen estructuras de control, sentenciasentre otros que facilitan al programador trabajar con tareasindependientes y variables de memoria compartida; abstraen casitotalmente (en su mayorıa) al programador de los detalles de laarquitectura del computador en donde trabaja.





ConceptoPequena historia

Pequena historia

Muchos lenguajes paralelos han prosperado a lo largo del tiempoen diferentes etapas de la historia de la programacion, peroninguno de ellos ha sido universalmente aceptado. El primero deellos fue Concurrent Pascal, disenado por Brinch Hansen en 1975como una extension del lenguaje Pascal, tambien daba soporte alparadigma concurrente.En estos anos la mayorıa de los lenguajes disenados eranextensiones de lenguajes secuenciales ya existentes. HighPerformance Fortran ha sido uno de los pocos lenguajes que haprevalecido en el tiempo, del que se ha originado nuevos lenguajescon este concepto y que se ha mantenido estable en el tiempo.





VentajasDesventajas

Ventajas

1 Facilitan la creacion de multiples tareas para a su vez estassean ejecutadas de manera independiente en cada procesador.

2 No requieres de paso de mensajes pues en su mayorıa trabajancon memoria compartida, esto es que cada tarea puedeacceder a las variables del programa pues todas ellas (lastareas) comparten el mismo espacio de memoria.

3 Muchas de las operaciones con procesos y subprocesos lasmaneja internamente el compilador.





VentajasDesventajas

Ventajas








VentajasDesventajas

Ventajas








VentajasDesventajas

Desventajas

1 Requiere por parte del programador el aprendizaje de unnuevo paradigma, reglas adicionales para programar, lo cualen muchos casos los mismos oponen resistencia al cambio.

2 No existe un gran apoyo para popularizar estos lenguajes, estocausa la discontinuidad del soporte para los mismos; sonmayormente utilizados en plataformas de super computacion,esto se debe que hasta no hace mucho la mayorıa de losordenadores personales poseıan un solo nucleo en la CPU.

3 Como aplican una capa extra para lo que significa operacionescon procesos, acceso a memoria compartida entre otras cosashace que en ocasiones no siempre el tiempo de ejecucion seael esperado (Tp ∼= Ts/n).





VentajasDesventajas

Desventajas








VentajasDesventajas

Desventajas








Analisis de DependenciaCondiciones de Bernstein

Analisis de Dependencia

Cuando trabajamos con un lenguaje paralelo se espera que elcompilador sea capaz de identificar problemas que evitan laejecucion concurrente.Los procesos no pueden ejecutarse juntos si entre ellos existenalguna dependencia que requiera el estricto orden de ejecucionsecuencial.Para ello el programador debe ser capaz de identificar lasdependencias que hay entre las instrucciones en los bloques de lasestructuras de control (vease forall), para garantizar que losprocesos que genera el compilador sean paralelos.





Analisis de DependenciaCondiciones de Bernstein

Condiciones de Bernstein

Tenemos dos conjuntos de posiciones de memoria:E(las entradas) y S(las salidas).Y tenemos a los procesos Pi .

Ei : Conjunto de posiciones de memoria leıdas por Pi .

Sj : Conjunto de posiciones de memoria leıdas por Pj .

Las condiciones son:

1 E1 ∩ S2 = φ.

2 E2 ∩ S1 = φ.

3 S1 ∩ S2 = φ.





ChapelRevisando ChapelAlgunos Ejemplos

Chapel

-Lenguaje de programacion paralela desarrollado en 2010 comoparte del proyecto Cray Cascade de Cray Company en SeattleWashington, disenado por David Callahan y su equipo dedesarrollo. Influenciado por High Performance Fortran y ZPL.






Revisando ChapelTipos de Datos

Chapel ofrece soporte a muchos tipos de datos, pero mostraremoslos mas importantes:

Tipo de Dato Dominio Declaracion

Booleano true o false var b: bool;Entero Int en 64 bits var n: int;Real Double en C o Java var n: real;

Cadena Tabla ASCII var s: string;Arreglos El maximo a almacenar var A: [l1..l2] (datatype);






Revisando ChapelEstructuras de control

Chapel ofrece soporte a las estructuras de control tradicionales,como if-else, selection (switch en lenguaje C), for-loop, while-loop,do while-loop, etc. Que con solo revisar el manual son faciles deidentificar y utilizar.Pero Chapel tambien ofrece soporte a estructuras de control conparalelismo implıcito.






Revisando ChapelEstructuras de control paralelas

Forall-loop:Similar al for secuencial, cuando el bucle inicia primero se creantantos hilos como nucleos de procesamiento existan para que cadauno de ellos ejecute un trozo de la tarea. Cada hilo tiene totalacceso a modificar las variables que en el bucle existan, por tantosi queremos que estas se modifique una vez por iteracionnecesitamos una variable de sincronizacion.-







Coforall-loop:Similar al forall solo que este creara un hilo de ejecucion por cadaentrada en el bucle, en caso de que el programador decida hacermas hilos que nucleos los hilos se someteran a la planificacion deprocesos del sistema operativo.-







Begin:Cada vez que llamas a begin este crea un hilo de ejecucion para lasinstrucciones que vienen a continuacion de el. El orden deejecucion puede variar.-







Cobegin:Similar al begin solo que lo que este dentro de la sentencia se tieneque ejecutar primero antes de lo que venga a continuacion en elcodigo.-







Variables de Sinconizacion:Son variables que bloquean al proceso que las llama hasta que suvalor le es asignado a otra variable del mismo tipo; ellas tienes dosestados: vacıas o llenas, cuando estan llenas estas bloquean a losotros procesos que las utilizan, llegan a estar vacıas cuando suvalor le es asignado a otra variable de sincronizacion.







Reduce:Esta operacion es similar a MPI Reduce, se compone de unaoperacion elemental, reduce y de un rango, esta rango puede serun arreglo o una serie de operaciones sobre los elementos de esearreglo. Cuando es llamada espera a todos los hilos que tenganparte de los valores de ese rango para ası aplicar la operaciongeneralizada sobre esos valores.-






Algunos Ejemplos

1 http:

//www.dropbox.com/s/1uyy93qa84g466p/primos.chpl

2 http://www.dropbox.com/s/eruglknlvn4h9d2/calculo_

pi.chpl

3 http://www.dropbox.com/s/cetdo6ifbqud5ul/

multiplicacion_matrices.chpl

4 http://www.dropbox.com/s/3k312fuiix324rb/

multiplicacion_matrices2.chpl


http://www.dropbox.com/s/1uyy93qa84g466p/primos.chpl

http://www.dropbox.com/s/1uyy93qa84g466p/primos.chpl

http://www.dropbox.com/s/eruglknlvn4h9d2/calculo_pi.chpl

http://www.dropbox.com/s/eruglknlvn4h9d2/calculo_pi.chpl

http://www.dropbox.com/s/cetdo6ifbqud5ul/multiplicacion_matrices.chpl

http://www.dropbox.com/s/cetdo6ifbqud5ul/multiplicacion_matrices.chpl

http://www.dropbox.com/s/3k312fuiix324rb/multiplicacion_matrices2.chpl

http://www.dropbox.com/s/3k312fuiix324rb/multiplicacion_matrices2.chpl




X10Revisando X10Un Ejemplo

X10

-Lenguaje de programacion paralela y orientado a objetosdesarrollado en 2004 por IBM en el centro de investigacionThomas J. Watson, disenado por Kemal Ebcioglu y su equipo dedesarrollo, influenciado principalmente por Java.






Revisando X10Tipos de Datos y Clases

X10 da soporte a todos los tipos basicos de Java, tales comoarreglos, enteros, reales, etc. E introduce el concepto deorientacion a objetos y jerarquıa de librerıas.Cada vez que escribamos un programa en X10 tenemos quecomenzar definiendo la clase tal y como hacemos en Java, ydefiniendo lo que queremos hacer en el public void main[](...).






Revisando X10Lugares y actividades

Un lugar es un repositorio donde interactuan n hilos con un trozode memoria compartida del todo en dicho lugar.Y una actividad es una sentencia que esta siendo ejecutada,independientemente, con sus propias variables locales, pudiera serpensada como un hilo ligero.En un lugar pueden haber muchas actividades, y en muchos lugarespueden haber actividades repetidas haciendo lo mismo con otrosdatos.






Revisando X10Relojes

Muchos algoritmos paralelos avanzan en fases, pero cada faseposee muchas actividades en accion, por tanto para garantizar quedichas actividades se ejecuten en una fase sin que en la fasesiguiente aun no se haya ejecutado todas las actividades de la faseanterior se utilizan los relojes, los cuales son una clase ya definidapor X10, con sus primitivas y metodos propios que avisan cuandotodas las actividades terminan su ejecucion para proceder a lasiguiente fase.






Revisando X10Arreglos distribuidos

X10 provee la clase DistArray, los cuales son arreglos queautomaticamente son distribuidos a trozos por la clase Dist amuchos lugares; estos trozos de los DistArrays se les llamanregiones.






Un Ejemplo

http://x10-lang.org/documentation/code-examples/

small-examples.html?id=103


http://x10-lang.org/documentation/code-examples/small-examples.html?id=103

http://x10-lang.org/documentation/code-examples/small-examples.html?id=103




Otros lenguajes paralelos

High Performance Fortran.

Cilk.

ZPL.

Parlog.

NESL.

Linda.

C*.





Otros lenguajes paralelos

SALSA.

Unified Parallel C.

Fortress.

Coarray Fortran (F–).

ParaSail.

Charm++.

Id.

SequenceL.

Ease.

FortranM.





Bibliografıa

Barry Wilkinson and Michael Allen. (1999). ParallelProgramming, Techniques and Applications using NetworkedWorkstations and Parallel Computers (2nd Edition). NewJersey: c©Prentice Hall.

Chapel: Overview. http://chapel.cray.com/

Chapel Tutorial.http://faculty.knox.edu/dbunde/teaching/chapel/

X10. http://x10-lang.org/

X10 Language Specification. http://x10.sourceforge.net/documentation/languagespec/x10-latest.pdf


http://chapel.cray.com/

http://faculty.knox.edu/dbunde/teaching/chapel/

http://x10-lang.org/

http://x10.sourceforge.net/documentation/languagespec/x10-latest.pdf

http://x10.sourceforge.net/documentation/languagespec/x10-latest.pdf

Education

Presentación - Lenguajes Paralelos