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  |