Comunicación No Estructurada Elementos 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
Checklist del diseño de comunicaciones 1) 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?
Aglomeración/Asignación Agrupació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
Aumento de la Granularidad Efecto Superficie-a-Volumen
Las comunicaciones son proporcionales a la superficie del subdominio, mientras que las computaciones lo son al volumen.
Aumento de la Granularidad Replicación de Computación Substitución de comunicaciones por computaciones redundantes Ejemplo: Reducción Paralela S = ? Xi N-1 i =0 0 2 1 3 1 0 3 2 S S S R R R 0 2 1 3 0 2 1 3 Soluciones sin replicación Array: 2(N-1) pasos Arbol:2logN pasos S S S S S S R R R R R R
Aumento de la Granularidad Replicación de Computación Ejemplo: Reducción Paralela Solución con replicación Mariposa: logN pasos
Aumento de la Granularidad Eliminación de Comunicaciones Aglomeración de tareas no concurrentes (ej., a diferentes niveles de una estruc- tura de computación) Ejemplo: Reducción Paralela Tareas no concurrentes aglomeradas 0 2 1 3 5 4 7 6 0 2 1 3 5 4 7 6 0 2 1 3 5 4 7 6 2 2 2 2 0 0 0 0 1 1 1 1 Hipercubo Mariposa Arbol 0 0 0 0 1 1 2 0 0 0 0 1 1 1 1 1 2 2 2 2
Perservando la flexibilidad No 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.
Reduciendo los costes de desarrollo Diferentes 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.
Checklist del diseño de la aglomeración 1) 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?
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
Proyección Estrategias de Proyección Descomposició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.
Algoritmo 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
Particionamiento por Bloques 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
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
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)
Bisección de Coordenadas Recursiva Procedimiento 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
Bisección Gráfica Recursiva Procedimiento 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
Bisección Espectral Recursiva Procedimiento 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
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.
Planificación de Tareas Caracterí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
Checklist del diseño de la proyección 1) 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)
| Página siguiente |