algoritmos paralelos

AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)

Diseño de algoritmos paralelos

AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro

Curso 2011-2012


Esquema del capítulo

• Visión general de algunos algoritmos serie.

• Algoritmo paralelo vs. Formulación

paralela

• Elementos de un Algoritmo paralelo• Elementos de un Algoritmo paralelo

• Métodos de descomposición:

– Extracción de la concurrencia.

• Métodos de asignación:

– Reducción de las comunicaciones por paralelismo.


Algunos algoritmos serie

• Multiplicación de matrices densas.

• Multiplicación de matrices dispersas.

• Eliminación Gausiana.• Eliminación Gausiana.

• Camino más corto (algoritmo de Floyd).

• Quicksort (ordenación rápida).

• Búsqueda de máximos y mínimos.

• Búsqueda heurística (problema del puzzle).


Multiplicación densa Matriz - Vector


Multiplicación densa Matriz - Matriz


Multiplicación Matriz dispersa - Vector


Eliminación Gausiana

La matriz A de un sistema de ecuaciones se reemplaza por una

matriz equivalente triangular superior


Camino más corto (algoritmo de Floyd)


Quicksort


Búsqueda del mínimo


Puzzle de 15 piezas


Algoritmo paralelo vs. Formulación paralela

• Formulación paralela: Paralelización de un

algoritmo serie ya diseñador. Adaptación a una

plataforma paralela.

• Algoritmo paralelo: Algoritmo que se diseña en • Algoritmo paralelo: Algoritmo que se diseña en

un inicio pensando en una plataforma paralela.

Puede diferir considerablemente de su versión

serie.

• En el curso, se trabajará principalmente con

Formulaciones paralelas.


Elementos de un algoritmo / formulación paralelo

• Elementos de trabajo que se pueden ejecutar

concurrentemente: Tareas.

• Asignación de tareas a múltiples procesadores.

• Distribución de la información (datos de entrada-salida • Distribución de la información (datos de entrada-salida

e intermedios) entre los procesadores.

• Gestión del acceso a datos compartidos.

• Sincronización de los procesos.

• Maximizar la concurrencia y minimizar costes

de comunicación: Mejorar el Speed-up.


Búsqueda de elementos de trabajo concurrentes

• Descomposición: Proceso de división del

trabajo en unidades menores y más manejables

denominadas tareas.

• Las tareas se definen a nivel de programación y • Las tareas se definen a nivel de programación y

se consideran indivisibles.


Ejemplo: Multiplicación Matriz densa - Vector

• Granularidad: Número y tamaño de las tareas.

• Granularidad fina: Muchas tareas detalladas.

• Granularidad gruesa: Pocas tareas genéricas.

Descomposición en n tareas Descomposición en 4 tareas


Ejemplo: Proceso de búsqueda


Ejemplo: Proceso de búsqueda

Dos descomposiciones de tareas, con resultados muy diferentes:

(a) Tres etapas de proceso, con un grado de concurrencia máximo de

4.

b) Cuatro etapas de proceso, con un grado de concurrencia máximo

de 4.

(a) (b)


Grafo de dependencia de tareas

• En la mayoría de los casos, las tareas tienen

dependencias. No pueden empezar hasta que no acaben

las predecesoras.

• Estas dependencias se representan mediante un grafo

dirigido acíclico, denominado Grafo de Dependencia dirigido acíclico, denominado Grafo de Dependencia

de Tareas.


Grafo de dependencia de tareas

• Grado medio de concurrencia: Número medio

de tareas que se pueden ejecutar

concurrentemente.

• Camino crítico: El camino más largo que recorre • Camino crítico: El camino más largo que recorre

el grafo, el cual delimita el tiempo de ejecución

total del algoritmo.

• Tanto el grado de concurrencia como el camino

crítico se ven directamente afectados por la

elección de la granularidad.


Grafo de interacción de tareas

• Muestra los patrones de interacción de las tareas.

• Suele contener al grafo de dependencias de tareas

como un subgrafo propio.

Multiplicación de matriz dispersa


Métodos habituales de descomposición

• Descomposición de datos.

• Descomposición recursiva.

• Descomposición exploratoria.• Descomposición exploratoria.

• Descomposición especulativa.

• Descomposición híbrida.


Descomposición recursiva

• Apropiado para problemas resolubles

con la técnica Divide-y-vencerás.

• Cada uno de los subproblemas • Cada uno de los subproblemas

generados en el proceso de división se

corresponde con un proceso.


Ejemplo: Quicksort

Cada paso de división se

asocia a un proceso.


Ejemplo: Cálculo del mínimo

Se puede aplicar la estrategia de divide-y-vencerás a problemas

que tradicionalmente no se han resuelto con esta técnica.


Descomposición de datos

• Apropiado para algoritmos que trabajan con

una gran cantidad de datos: el problema está

en el volumen.

• Habitualmente se realiza en dos etapas:

– Partición de los datos.

– Cambio en la computación para trabajar con múltiples

particiones de datos.

• ¿Qué datos hay que dividir en particiones (los de

entrada, los intermedios)?: Depende del caso.


Ejemplo: Multiplicación de matrices

• Partición de los datos de salida:


Ejemplo: Multiplicación de matrices

• Partición de los datos intermedios:

Grafo de dependencias de datos


Descomposición exploratoria

• Apropiado para descomponer cálculos

basados en la búsqueda de un espacio

de soluciones.de soluciones.



• Puede resultar en speed-up anómalo:

– Dependiendo de dónde se encuentre la solución

dentro del espacio, la formulación paralela puede

requerir más trabajo que la formulación serie.

Speed-up anómalo debido a descomposición exploratoria

requerir más trabajo que la formulación serie.


Descomposición especulativa

• Usada para extraer concurrencia en

problemas donde el próximo paso es una

acción (entre varias posibles), que sólo se

puede determinar cuando la tarea actual puede determinar cuando la tarea actual

concluya.

• Esta descomposición asume un cierto

resultado de la tarea actual y ejecuta los

pasos posteriores.

– Equivalente a la ejecución especulativa a nivel de

microprocesador


Ejemplos: Simulación discreta de eventos


Descomposición especulativa

• Si la predicción es errónea:

– el trabajo realizado se desperdicia

– puede que haya que deshacer los resultados de la

tarea (restauración de contexto)tarea (restauración de contexto)

• A menudo, puede ser el único medio para

obtener concurrencia.


Asignación de tareas

• ¿Por qué una asignación de tareas? ¿No es

suficiente una asignación aleatoria?

• La asignación apropiada es crítica, a fin de • La asignación apropiada es crítica, a fin de

minimizar el coste asociado al paralelismo.

• Coste = p·Tp - Ts.

• Causas del coste:

– Carga de trabajo no equilibrada.

– Comunicación entre procesos.


Asignación de tareas

• Para una correcta asignación hay que

estudiar los grafos de dependencia e

interacción de tareas:interacción de tareas:

– ¿Se conocen las tareas a priori?

– ¿Y sus requisitos de cálculo?

– ¿Cuántos datos se asociarán por tarea?

– ¿Cómo se comunican las tareas?

Dependencia

de datos

Interacción


Ejemplos: Interacción simple y compleja

Interacción simple: Las

tareas se comunican sólo

con las adyacentes

Interacción compleja:

Las tareas necesitan

mucha comunicación


Objetivo: Equilibrado de carga

• El equilibrado de carga es fundamental para

maximizar la concurrencia.

• Una asignación equitativa de tareas a

procesadores no garantiza el equilibrado de procesadores no garantiza el equilibrado de

carga.


Técnicas de equilibrado de carga

• Asignación estática:

– Las tareas se distribuyen entre los procesadores antes de la

ejecución.

– Aplicable a tareas:

• Generadas estáticamente• Generadas estáticamente

• Con requisitos computaciones conocidos

• Asignación dinámica:

– Las tareas se distribuyen entre los procesadores en tiempo de

ejecución.

– Aplicable a tareas:

• Generadas dinámicamente

• Con requisitos computaciones desconocidos


Técnicas de equilibrado de carga

• Asignación estática:

– Distribución en array

– Particionamiento del grafo– Particionamiento del grafo

• Asignación dinámica:

– Patrones centralizados

– Patrones distribuidos


Asignación estática: Distribución en array

• Apropiada para algoritmos:

– que usan descomposición de datos

– sus datos se almacenan en forma de arrays– sus datos se almacenan en forma de arrays

• Tipos:

– Distribución en bloques

– Distribución cíclica

– Distribución cíclica en bloques

– Distribución aleatoria en bloques


Ejemplo: Distribuciones en bloques

8 procesos

16 procesos


Ejemplo: Distribuciones en bloques

Partición

unidimensional2n

p

n2

22

np

n +

Partición

bidimensional

Los datos de las zonas sombreadas A y B son requeridos por el proceso que

calcula la zona sombreada C. La partición unidimensional requiere más acceso a

datos que la bidimensional.

p

n2

p

n2

p

n22


Ejemplo: Distribuciones cíclicas en bloques

• Se usa para evitar problemas de desequilibrio de carga cuando

distintas partes del array necesitan carga computacional distinta.

•Se divide el array en más bloques que procesadores.

•Cada procesador se encarga de varios bloques no contiguos.

Distribuciones uni y

bidimensionales sobre 4

procesos

Ej.: Eliminación Gausiana.


Distribuciones aleatorias en bloques

• Algunas veces, la computación se realiza únicamente

sobre ciertas partes del array:

– por ejemplo, en la multiplicación de matrices dispersas.

El uso de distribución

cíclica en bloques llevaría

a un desequilibrio de

carga


Distribuciones en bloques aleatorios

Distribución aleatoria

unidimensional

Distribución aleatoria bidimensional: Mejor equilibrado de carga.


Particionamiento del grafo

• La asignación de procesos se puede

conseguir particionando directamente el

grafo de interacción de tareas.

• Ejemplo: Modelado basado en cálculos sobre malla.• Ejemplo: Modelado basado en cálculos sobre malla.



Distribución aleatoria en

8 procesos

Carga equidistribuida

Distribución en 8 procesos

usando un algoritmo de

particionamiento de grafos

Carga equidistribuida+

Minimización de comunicaciones



Otro ejemplo: Multiplicación de matriz dispersa

Asignación contigua,

Cada proceso se

ocupa de 4 filas

consecutivas consecutivas

Asignación que minimiza las

comunicaciones y mantiene

las misma carga

computacional por proceso


Patrones de equilibrado dinámico de carga

• Tema de máxima actualidad a nivel de

investigación.

• Patrones centralizados:

– Un cierto procesador es responsable de repartir el

trabajo.

• Patrones distribuidos:

– El trabajo se puede distribuir entre cualquier par de

procesadores.


Asignación para minimizar los costes de interacción

• Maximizar ubicación conjunta de datos.

• Minimizar volumen de intercambio de datos.

• Minimizar frecuencia de interacción.

• Minimizar contención y hot spots.• Minimizar contención y hot spots.

• Solapar computación y comunicación.

• Réplica selectiva de datos y cálculo.

Estos objetivos se consiguen con una buena

descomposición y asignación de tareas.

algoritmos paralelos

Documents