Metodología de Diseño
Etapas de la Paralelización Partició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.
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.
Descomposició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.
Descomposición Funcional Mé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 Atmosférico Modelo Hidrológico Modelo Oceánico Modelo de Superficie Terrestre Modelo Climático
Ejemplo de descomposición funcional Procedure 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 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. 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.
Checklist de la partición 1) 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?
Coordinación Comunicació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
Esquemas 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. Categorización de las necesidades de comunicación 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
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
Comunicación Global Reducción Paralela S = ? Xi N-1 i =0 S 0 2 1 3 5 4 7 6 0 2 1 3 5 4 7 6 0 1 2 3 4 5 6 7 Algoritmo Centralizado y Secuencial 6 5 4 3 2 1 0 Algoritmo Distribuido (segmentado)
0 2 1 3 5 4 7 6 S S S S S S S 1 1 1 1 2 2 0 0 0 0 0 0 0 0 Algoritmo Divide &Conquer
| Página siguiente |