Procesamiento ParaleloPrincipios de diseno de algoritmos paralelos

Javier Iparraguirre

Universidad Tecnologica Nacional, Facultad Regional Bahıa Blanca11 de Abril 461, Bahıa Blanca, Argentina

jiparraguirre@frbb.utn.edu.ar

http://www.frbb.utn.edu.ar/hpc/

25 de marzo de 2016

Marco Conceptual

Lo que Viene [1]

• Conceptos Iniciales• Tecnicas de decomposicion• Tareas e Interacciones• Mapeo y Balance de Carga• Metodos para Contener las Perdidas por Interacciones• Modelos de Algoritmos Paralelos

Conceptos Iniciales

Multiplicacion de Matriz-vector Densa

Puntos a Tener en Cuenta

y [i] =n∑

j=1

A[i , j] ∗ b[j] | y = A ∗ b

• Tareas: n tareas de multiplicar una fila de la matriz por elvector

• Grafo de dependencia: no hay dependencia de tareas• ¿Decomposicion? (grafo de decomposicion)

Granularidad

Granularidad

• Tenemos procesos (o tareas) y procesadores (no es lomismo!)

• La granularidad es el tamano de la tarea asignada a cadaprocesador

• Podemos de hablar de granularidad fina o gruesa• Hay relacion entre el grado de concurrencia y la

granularidad• Extrema granularidad trae problemas de perdidas en las

comunicaciones!!

Camino crıtico

• Un grafo de dependencias es importante para laasignacion de tareas

• El camino critico es fundamental• El tiempo de procesamiento esta muy relacionado al largo

del camino crıtico

• ¿Cuales son los pasos para hacer un asado? ¿Hayparalelismo?

Camino crıtico

• Un grafo de dependencias es importante para laasignacion de tareas

• El camino critico es fundamental• El tiempo de procesamiento esta muy relacionado al largo

del camino crıtico• ¿Cuales son los pasos para hacer un asado? ¿Hay

paralelismo?

Camino Crıtico

Multiplicacion Matrix-vector Suelta (sparse)

y [i] =n∑

0<j<n,A[i,j] 6=0

A[i , j] ∗ b[j]

• No podemos hacer una multiplicacion si A[i,j] es 0• Dependiendo del conjunto de datos, hay un grafo de

dependencias• No es conveniente asignar tareas a procesadores de

forma aleatoria• Hay dos temas que entran en juego: scheduling and

mapping (lo vemos mas adelante)

Multiplicacion Matriz-vector Suelta (sparse)

Tecnicas de Decomposicion

Tecnicas de Decomposicion

• Recursiva• Datos• Exploratoria• Especulativa

Decomposicion Recursiva (1 de 2)

Decomposicion Recursiva (2 de 2)

• Estrategia divide y conquistaras (divide and conquer)• Se parte el problema en problemas mas chicos

Decomposicion por Datos (1 de 3)

Decomposicion por Datos (2 de 3)

Decomposicion por Datos (3 de 3)

• Hay dos pasos en la decomposicion• Se particionan los datos• Las particiones se convierten en tareas

Decomposicion Exploratoria (1 de 3)

Decomposicion Exploratoria (2 de 3)

Decomposicion Exploratoria (3 de 3)

• Hay dos pasos en la decomposicion• Funciona muy bien para problemas que involucran

busquedas• Se particiona el espacio de busqueda en espacios

menores y se busca en paralelo

Decomposicion Especulativa (1 de 2)

Decomposicion Especulativa (2 de 2)

• Cuando un programa puede tomar varios caminosposibles en funcion de los computos

• Similar a evaluar un switch en C• No es eficiente paralizar todos los casos, solo los mas

frecuentes• Tiene mucho valor cuando se agregan varias etapas de

especulacion

Mapeo y Balance de Carga

Mapeo y Balance de Carga

• El mapeo se hace para balancear la carga• Tambien se tiene en cuenta la interaccion entre tareas• Hay dos formas de mapeo: estatico y dinamico• Mapeo estatico

• Datos• Tareas

• Mapeo dinamico• Centralizado• Distribuido

Mapeo Estatico por Datos

Mapeo Estatico por Tareas

Mapeo Estatico Modelo Real (1 de 3)

Mapeo Estatico Modelo Real (2 de 3)

Mapeo Estatico Modelo Real (3 de 3)

Mapeo Dinamico

• Cuando la carga de trabajo varıa con los computos• Cuando hay gran desbalance o el grafo de dependencia es

dinamico• Centralizado

• Arquitectura maestro-esclavo• Facil de mantener• Pude tener problemas de escalabilidad

• Distribuido• Un conjunto de tareas es distribuida entre procesos• Cada proceso puede recibir o enviar tareas a un par• Soluciona problemas de escalabilidad

Metodos para Contener las Perdidas(overheads) por Interacciones

Metodos para Contener las Perdidas (overheads) porInteracciones

• Maximizar la localıa de los datos• Minimizar contencion y puntos calientes (hot-spots)• Solapar computacion con interacciones• Replicar los datos o los computos• Usar operaciones de interaccion colectivas optimizadas• Solapar interacciones con otras interacciones

Modelos de Algoritmos Paralelos

Modelos de Algoritmos Paralelos

• Paralelismo de datos• Grafo de tareas• Conjuto de trabajadores (work pool)• Maestro-esclavo (master-slave)• Productor-consumidor (pipeline producer-consumer)

Paralelismo de Datos

• Las tareas son mapeadas de manera cuasi-estatica• Las operaciones paralelas son muy similares• Necesita poca sincronizacion y asignacion

Grafo de Tareas

• Generalmente se usa cuando tenemos grandesvolumenes de datos

• Usualmente se mapean estaticamente

Conjunto de Trabajadores (work pool)

• Mapeo dinamico de tareas a procesos• Muy util para el balance de carga• El mapero puede ser centralizado o descentralizado

Maestro-esclavo (master-slave)

• Un maestro genera trabajo y los esclavos ejecutan• Problemas de cuellos de botella

Productor-consumidor (pipeline producer-consumer)

• Una secuencia de datos pasa a traves de una serie deprocesos

• Cada proceso realiza una tarea particular• Todos los procesos actuan a la vez formando una canerıa

(pipeline)

Resumen

Nota Personal

• Vimos herramientas de decomposicion, interacciones,mapeos, perdidas y modelos de algoritmos

• Son solo herramientas clasicas para orientarnos (ejesortonormales en un espacio de las fases conceptual)

• Dependiendo el problema se encuentra la solucion• Son fundamentales las herramientas de diagnostico

(profiling)

Contacto

¡Muchas gracias!

¿Preguntas?jiparraguirre@frbb.utn.edu.ar

Referencias

[1] G. Ananth, G. Anshul, K. George, and K. Vipin.Introduction to parallel computing, 2003.