1 Programación Paralela

2 Metodología de Diseño

3 Etapas de la ParalelizaciónPartición/Descomposición: La computación se descompone en pequeñas tareas que forman las unidades de concurrencia. Coordinación: Incorporación de mecanismos para la denominación, comuni- cación y sincronización de las tareas. Aglomeración/Asignación: Las tareas se agrupan en procesos más grandes para optimizar el rendimiento y/o reducir costes de desarrollo. Proyección: Los procesos se asignan a los procesadores disponibles de forma que se maximice la utilización y minimice los costes de comunicación.

4 Partición/Descomposición¿Cómo particionar la Computación? Código Estructurado: Sugerido por el código mismo (lazos, estructuras de datos, ..) Código no Estructurado: Siempre se puede recurrir a heurísticas dinámicas. ¿Qué ocurre con los datos? Pase de Mensajes: Deben particionarse con las computaciones (localidad) Memoria Compartida: La localidad es siempre un factor de rendimiento Estrategias de Particionamiento Descomposición en Dominios : Se particionan las estructuras de datos y se generan las tareas a partir de las computaciones asociadas a cada partición. Descomposición Funcional : Se particionan las computaciones en tareas funcionales y se asocian los datos maximizando la localidad.

5 Estilo usual en la programación SPMDDescomposición en Dominios Método: 1. Los datos se particionan en grupos pequeños de tamaño similar 2. Se diseñan las tareas, a partir de cada uno de los grupos anteriores y todas sus computaciones asociadas. Estilo usual en la programación SPMD Elección de los Datos: Es preferible la mayor estructura de datos o la que se accede con mayor frecuencia En códigos grandes puede ser más eficiente manejar varias descomposiciones diferentes.

6 Descomposición FuncionalMétodo: 1. Las computaciones se descomponen en tareas disjuntas 2. Los datos se estructuran en función de las tareas diseñadas En computación numérica, es más usual la descomposición en dominios. La descomposición funcional se suele combinar con la descomposición en dominios en una jerarquía en dos niveles. Modelo Climático Modelo Atmosférico Modelo Hidrológico Modelo Oceánico Modelo de Superficie Terrestre

7 Ejemplo de descomposición funcionalProcedure search (A) begin if (solution (A) ) then score = eval (A) report solution and score else foreach child A (i) of A search (A(i)) endfor endif end Task estructure for the search example. Each circle represents a node in the search tree and hence a call to the search proce- dure. A task is created for each node in the tree as it is explored. At any one time, some tasks are actively engaged in expanding the tree further (these are shaded in the figure); others have reached solution nodes and are terminating, or are waiting for their offspring to report back with solutions. The lines re- present the channels used to return solutions. Algorithm 1.1 A recursive formulation of a simple search algorithm. When called to expand a search tree node, this procedure checks to see whether the node in question represents a solution. If not, the algorithmmakes recur- sive calls to the same procedure to expand each of the offspring nodes.

8 Checklist de la partición1) Define su partición al menos un order de magnitud más de tareas que procesadores en su sistema paralelo? 2) Elimina su partición redundancia en computación y almace- namiento? 3) Son las tareas de tamaño comparable? 4) Escala el número de tareas con el tamaño del problema? 5) Ha identificado varias particiones alternativas?

9 Coordinación Algunos lenguajes modernos (ej., lenguajesComunicación/Sincronización: Memoria compartida: Mientras la comunicación es implícita, la sincroniza- ción suele implementarse mediante construcciones específicas (exclusión mutua y sincronización de sucesos) Pase de Mensajes: La comunicación y sincronización de sucesos utilizan el mismo mecanismo (mensajes explícitos), mientras que la exclusión mutua se verifica por defecto. Algunos lenguajes modernos (ej., lenguajes de paralelismo de datos) hacen transparente la comunicación y sincronización explícita Influencia de la Descomposición Descomposición en Dominios: La organización eficiente de la comunicación es usualmente compleja, debido a las dependencias entre las tareas. Descomposición Funcional: La organización eficiente de la comunicación es inmediata, consecuencia directa de la descomposición y corresponde al flujo de datos entre tareas

10 Esquemas de ComunicaciónCategorización de las necesidades de comunicación Comunicación Local/Global Comunicación Local: Cada tarea se comunica con pocas tareas Comunicación Global: Cada tarea se comunica con muchas ( o todas las) tareas. Comunicación Estructurada/No estructurada Comunicación Estructurada: Una tarea y sus vecinos forman una estructura regular Comunicación No estructurada: El patrón de comunicaciones es irregular. Comunicación Estática/Dinámica Comunicación Estática: La identidad de las tareas comunicantes no cambia con el tiempo Comunicación Dinámica: El patrón de comunicaciones cambia durante la ejecución del programa. Comunicación Síncrona/Asíncrona Comunicación Síncrona: Los productores y consumidores operan de forma coordinada (cooperan) Comunicación Asíncrona: El consumidor obtiene datos sin la cooperación del productor

11 Coordinación Debemos establecer el acceso a datos, y la comunicación y sin- cronización entre las tareas. Alternativas Memoria Compartida: Los datos se distribuyen a lo largo del espacio de memoria física, y la comunicación/sincronización se produce implícitamente a través de variables definidas en el espacio compartido. Pase de mensajes: Los datos deben distribuirse explícitamente en las memo- rias locales y la comunicación/sincronización debe establecerse explícitamente (las tareas deben saber cómo están distribuidos los datos) La distribución de datos no es esencial en un modelo de memoria compartida, pero sí recomendable

12 Comunicación Global Reducción Paralela S =  Xi S 1 2 3 4 5 6 7 1 2 3Algoritmo Centralizado y Secuencial 1 2 3 4 5 6 7 Algoritmo Distribuido (segmentado) 1 2 3 4 5 6 7

13 S S S S S S S 1 2 3 4 5 6 7 Algoritmo Divide &Conquer 0 0 0 0 0 0 0 0 S S S S S S 1 2 3 4 5 6 7

14 Comunicación No EstructuradaElementos Finitos en Ingeniería Patrón de comunicaciones complejo, que puede variar con el tiempo Se complican las operaciones de aglomeración/asignación y proyección

15 Checklist del diseño de comunicaciones1) Realizan todas las tareas aproximadamente el mismo número de comunicaciones? 2) Cada tarea se comunica sólo con un pequeño número de ve- cinos? 3) Pueden proceder las operaciones de comunicación de forma simultánea? 4) Los cálculos asociados a diferentes tareas, puede proceder concurrentemente?

16 Aglomeración/AsignaciónAgrupación de Tareas en Procesos: El número de procesos puede diferir del número de procesadores (multipro- gramación) Interacción entre procesos pertenecientes a diferentes aplicaciones El número de procesos puede variar durante la ejecución de la aplicación La aglomeración especifica un mecanismo por el cual las tareas se asignan a procesos, o son seleccionadas por los procesos durante la ejecución Criterios que guían la Aglomeración: Aumento de la Granularidad: Los costes de comunicación, sincronización y y creación/gestión de procesos influyen críticamente en el rendimiento paralelo. Flexibilidad/Escalabilidad Costes de Desarrollo

17 Aumento de la GranularidadEfecto Superficie-a-Volumen Las comunicaciones son proporcionales a la superficie del subdominio, mientras que las computaciones lo son al volumen.

18 Aumento de la GranularidadReplicación de Computación Substitución de comunicaciones por computaciones redundantes Ejemplo: Reducción Paralela N-1 S =  Xi i =0 Soluciones sin replicación Array: 2(N-1) pasos S S S R R R 1 2 3 1 2 3 Arbol:2logN pasos S S R R S S R R R R S S 1 2 3 1 2 3

19 Aumento de la GranularidadReplicación de Computación Ejemplo: Reducción Paralela Solución con replicación Mariposa: logN pasos

20 Aumento de la GranularidadEliminación de Comunicaciones Aglomeración de tareas no concurrentes (ej., a diferentes niveles de una estruc- tura de computación) Ejemplo: Reducción Paralela 2 Tareas no concurrentes aglomeradas 1 1 Arbol 1 2 3 4 5 6 7 2 2 2 2 Mariposa 1 1 1 1 1 1 2 3 4 5 6 7 1 5 7 4 6 1 Hipercubo 2 2 2 2 1 1 3 2 1

21 Perservando la flexibilidadNo restringir innecesariamente la escalabilidad del algoritmo (la descomposición multidimensional es crítica) La capacidad de crear un número variable de tareas es crítica para asegurar la portabilidad y escalabilidad (permite realizar tareas como simultanear computación y comunicación) Todavía requerimos que haya más tareas que procesadores para ase- gurar una buena capacidad de balancear la carga La granularidad puede controlarse en tiempo de compilación o de ejecución.

22 Reduciendo los costes de desarrolloDiferentes estrategias de partición suelen tener costes de desarrollo distintos (seleccionar aquella que evite cambios extensos en el código) Normalmente los algoritmos paralelos forman parte de grandes aplicaciones, por tanto hay que evaluar los costes de integración con los restantes módulos de la aplicación.

23 Checklist del diseño de la aglomeración1) Ha reducido la aglomeración los costes de comunicaciones aumentando la localidad?. Sino, estudie otra estrategia. 2) Si la aglomeración ha replicado computaciones (y datos), verifique que ésto es eficiente para un amplio abanico de problemas y plataformas. 3) Si ha replicado los datos, compruebe que ésto no restringe la escalabilidad de la aproximación 4) Son las tareas resultantes de similar costo en comunicaciones y computación? 5) El número de tareas aglomeradas, todavía escala con el tamaño del problema? 6) Si la aglomeración ha eliminado oportunidades de ejecución simultánea, ha verificado si todavía hay suficiente concurrencia para un rango amplio de pla- taformas? 7) Puede reducirse el número de tareas aún mas? 8) Si está paralelizando un código secuencial existente, ha evaluado sus costes?. Si son altos, ha considerado otras estrategias totalmente diferentes?

24 Proyección La proyección es Crítica en Máquinas Escalables Aspectos de la Proyección de Procesos ¿Qué procesos deben ejecutarse en el mismo procesador? (multiprogramación,…) ¿Qué procesos se ejecutan en un procesador concreto? Estrategias de Proyección Situar procesos concurrentes en procesadores diferentes (potenciar la concu- rrencia) Situar procesos que comunican frecuentemente en el mismo procesador (po- tenciar la localidad) El problema de la Proyección es NP-Completo

25 Proyección Estrategias de ProyecciónDescomposición Estructurada en Dominios: Proyección directa, minimizando comunicaciones. Descomposición No-Estructurada Estática en Dominios: Heurística de proyección con algún esquema estático de balanceo de la carga. Descomposición No-Estructurada Dinámica en Dominios: Heurística de proyección con algún esquema dinámico de balanceo de la carga Descomposición Funcional:Heurística de proyección con algún esquema de planificación de tareas estático o dinámico.

26 de la Carga ComputacionalAlgoritmo de Balanceo de la Carga Computacional Técnicas especialmente diseñadas para desarrollar programas paralelos SPMD basados en la descomposición de dominios. Engloban las fases de particionamiento, aglomeración y pro- yección, y suelen denominarse algoritmos de particionamiento. Aproximaciones Representativas Algoritmos Regulares Estáticos - Particionamiento por Bloques - Particionamiento Cíclico (scattered) Algoritmos Irregulares Estáticos - Bisección Recursiva Algoritmos Dinámicos - Algoritmos Locales - Métodos Probabilísticos

27 Particionamiento por BloquesCaracterísticas Los procesos tienen una duración temporal determinable durante la fase de compilación Las comunicaciones son estructuradas (regulares) Modelo de Programación: SPMD estático

28 Particionamiento Cíclico (Scattered)Características Los procesos tienen una duración temporal determinable durante la fase de compilación Las comunicaciones son estructuradas (regulares) Modelo de Programación: SPMD estático

29 Bisección Recursiva Características Los procesos tienen una duración temporal determinable durante la fase de compilación Las comunicaciones son no estructuradas (irregulares) Modelo de Programación: SPMD estático Técnicas de Bisección Recursiva Bisección de Coordenadas Recursiva: Descomposición del dominio en fun- ción de la distancia Euclidiana entre sus elementos (las comunicaciones no son optimizadas) Bisección Gráfica Recursiva: Descomposición del dominio en función de la conectividad entre sus elementos (reduce las necesidades de comunicación) Bisección Espectral Recursiva: Descomposición del dominio en función de sus propiedades espectrales (mejora la compacidad de los subdominios)

30 Bisección de Coordenadas RecursivaProcedimiento 1. Determina la expansión más larga del dominio 2. Ordena los nodos de acuerdo con la coordenada seleccio- nada 3. Asigna la mitad de los nodos ordenados a cada subdo- minio 4. Repite recursivamente

31 Bisección Gráfica RecursivaProcedimiento 1. Determina dos nodos periféricos del dominio 2. Ordena el resto de los nodos según la distancia gráfica a los nodos seleccionados 3. Asigna la mitad de los nodos ordenados a cada subdo- minio 4. Repite recursivamente

32 Bisección Espectral RecursivaProcedimiento 1. Determina el vector de Fiedler del dominio usando el algoritmo de Lanczos 2. Ordena los nodos de acuerdo con el tamaño de los ele- mentos del vector de Fiedler 3. Asigna la mitad de los nodos ordenados a cada subdo- minio 4. Repite recursivamente

33 Algoritmos Locales (Dinámicos)Características Los procesos tienen una duración temporal no determinable durante la fase de compilación Solución Los procesadores comparan periódicamente su carga compu- tacional, y establecen una redis- tribución para balancearla.

34 Planificación de TareasCaracterísticas Muchas tareas con requerimientos débiles de localidad Distribución de Tareas entre Procesadores Conflicto entre ejecución independiente (reducir costes de comunicación) y conocimiento global del estado de computación (mejorar el balanceo de la carga) Esquemas de Planificación Centralizado: Gestor/Trabajador Distribuido: Las tareas se distribuyen entre los procesadores y se ejecu- tan de forma cooperativa dinámica. Problema de la Terminación de la Ejecución

35 Checklist del diseño de la proyección1) Si ha considerado un diseño SPMD y es muy complejo, ha considerado uno basado en la creación dinámica de tareas?. Lo recíproco. 2) Si usa un esquema de balanceo de la carga centralizado, ha verificado que el master no es un cuello de botella? 3) Si usa un esquema dinámico de balanceo de la carga, ha eva- luado su costo?. Intente usar esquema cíclicos o probabilísticos. 4) Si usa un esquema probabilístico, tiene un número razonable de tareas? (al menos 10 veces más que procesadores)