COMPUTACIÓN DE ALTO
RENDIMIENTO
Tema 3 - módulo 2 – Metodología
de Programación Paralela
Departamento de Ingeniería Informática 1
Universidad Francisco de Vitoria
Computación de Alto Rendimiento
Para ir del algoritmo secuencial al paralelo:
Computación de Alto Rendimiento
Romper bucles
si genero muchas tareas
si genero pocas tareas
tiempo en serio/tiempo en paralelo
Computación de Alto Rendimiento
vemos los bucles for y vemos si
pueden ser paralelizados o no. Esto
dependerá de los datos que utiliza
cada bucle
este bucle externo si se
podria lanzar en paralelo
esto no se
va a poder
paralelizar
Descomposición de la multiplicación
matricial-vectorial densa en n tareas, donde
n es el número de filas de la matriz.
Se resaltan las partes de la matriz y los 1 proceso por cada fila
vectores de entrada y salida a los que se
accede mediante la Tarea 1.
4
Computación de Alto Rendimiento
cada tarea hace un 25% de las filas por ejemplo
Computación de Alto Rendimiento
Un gestor de base de datos: divide nuestra query en queries más peq que se ejecutan en paralelo y
dsps se unen para generar la respuesta
Computación de Alto Rendimiento
En general, para los gráficos de dependencia de tareas que son árboles,
el grado máximo de concurrencia siempre es igual al número de hojas del árbol. 7
Computación de Alto Rendimiento
Un indicador más útil del rendimiento de un programa paralelo es el grado medio de concurrencia, que es
el número medio de tareas que se pueden ejecutar simultáneamente durante toda la duración de la
ejecución del programa.
camino con mayor coste
Pesos al
coste de
las tareas
Tambien se le
podria poner
un peso a la
flecha (mas
completo)
63/27=2,33
63=10*4+9+6+8 Grado medio de concurrencia: de media,
27=10+9+8 cuantos procesos han estado activos a
la vez de forma concurrente 8
Computación de Alto Rendimiento
instante en el que hay mayor numero de tareas lanzadas
En el ejercicio anterior, 4, al principio del todo
Solo entender el concepto
Matriz que
plasma la
interacción del
grafo dirigido
los nodos y aristas de un gráfico de interacción de tareas se les pueden asignar pesos proporcionales a la
cantidad de cómputo que realiza una tarea y la cantidad de interacción que ocurre a lo largo de un borde, si se
conoce esta información. 9
Computación de Alto Rendimiento
Un buen mapeo debe buscar
maximizar el uso de la
concurrencia al mapear
tareas independientes en
diferentes procesos, debe
buscar minimizar el tiempo
total de finalización
asegurando que los
procesos estén disponibles
para ejecutar las tareas en la
ruta crítica tan pronto como
dichas tareas se vuelvan
ejecutables
10
Computación de Alto Rendimiento
Proceso completo
11
Computación de Alto Rendimiento
Técnicas de descomposición
Explicadas abajo
12
Computación de Alto Rendimiento
Descomposición recursiva
13
Computación de Alto Rendimiento
Ejemplo descomposición recursiva
El gráfico también
representa el grafo de
tarea para el problema.
Inicialmente, solo hay
una secuencia (es decir,
la raíz del árbol), y
podemos usar solo un
proceso para
particionarlo. La
finalización de la tarea
raíz da como resultado
dos subsecuencias (A0 y
A1, correspondientes a
los dos nodos del primer
nivel del árbol) y cada
una puede particionarse
en paralelo. De manera
similar, la concurrencia
continúa aumentando a
medida que avanzamos
en el árbol.
14
Computación de Alto Rendimiento
A veces, es posible reestructurar un algoritmo para hacerlo susceptible a la
descomposición recursiva incluso si el algoritmo comúnmente utilizado para el
problema no se basa en la estrategia divide y vencerás.
1. procedure SERIAL_MIN (A, n)
2. begin
3. min = A[0]; Un programa en serie
4. for i := 1 to n - 1 do para encontrar el mínimo
5. if (A[i] < min) min := A[i]; en una matriz de números
6. End for; A de longitud n.
7. return min;
8. end SERIAL_MIN
En este caso dividimos la secuencia A en dos subsecuencias, cada una de tamaño n/2, y
encontramos el mínimo para cada una de estas subsecuencias realizando una llamada
recursiva. Ahora el elemento mínimo general se encuentra seleccionando el mínimo de
estas dos subsecuencias. La recursión termina cuando solo queda un elemento en cada
subsecuencia.
15
Computación de Alto Rendimiento
El gráfico de dependencia de tareas para encontrar el número mínimo en la secuencia {4, 9,
1, 7, 8, 11, 2, 12}. Cada nodo en el árbol representa la tarea de encontrar el mínimo de un
par de números. Cada tarea encuentra el mínimo de un par de números
16
Computación de Alto Rendimiento
Descomposición de datos
17
Computación de Alto Rendimiento
Descomposición de datos: salida
18
Computación de Alto Rendimiento
La regla "El dueño calcula"
Una descomposición basada en la partición de los datos de salida o de entrada también se conoce
ampliamente como la regla “el dueño calcula”.
19
Computación de Alto Rendimiento
Descomposción de datos: intermedios
20
Computación de Alto Rendimiento
Descomposción exploratoria
21
Computación de Alto Rendimiento
Descomposción exploratoria
Solo admite 2 o 3 niveles, porque sino peta
Puzzle 15
22
Computación de Alto Rendimiento
Anomalía en la descomposición exploratoria
Consideremos un espacio de búsqueda que se ha dividido en cuatro tareas simultáneas, como
se muestra. Si la solución se encuentra justo al comienzo del espacio de búsqueda
correspondiente a la tarea 3 , la formulación paralela la encontrará casi inmediatamente. El
algoritmo serial habría encontrado la solución solo después de realizar un trabajo equivalente a
buscar en todo el espacio correspondiente a las tareas 1 y 2. Por otro lado, si la solución se
encuentra hacia el final del espacio de búsqueda correspondiente a la tarea 1, entonces la
formulación en paralelo realizará casi cuatro veces el trabajo del algoritmo en serie y no
producirá aceleración.
23
Computación de Alto Rendimiento
Descomposción especulativa
24
Computación de Alto Rendimiento
Asignación de tareas Muy dificil asignar los datos de forma equitativa en estos casos
medir la ineficiencia de la ejecucion paralela con respecto a la ejecucion en serie. p=num procesadores. Tp tiempo paralelo. Ts tiempo serie. En el caso ideal será 0.
Tp =Ts/p porque se iguala a 0.
nº de tareas estático o nº de tareas dinámico (elegimos el pivote de manera dinámica
y no tiene por qué estar en medio)--> no se cuantos procesos voy a necesitar
volumen de datos de cada tarea
es algo fijo.
no siempre se saben las flechas de comunicacion del grafo. A veces se van deduciendo a medida que avanza el algoritmo.
Un patrón de interacción se considera regular si tiene alguna estructura que pueda explotarse
para una implementación eficiente. Por otro lado, un patrón de interacción se llama irregular si
no existe tal patrón regular.
25
Computación de Alto Rendimiento
Interacción simple vs. compleja
26
Computación de Alto Rendimiento
El problema de asignación
reducir
Cuanto mayor num de procesadores mejor y
asignar una carga de trabajo equitativa a cada de
ellos
evitar que haya procesadores que se queden ociosos, es decir, sin carga de trabajo
27
Computación de Alto Rendimiento
El problema de asignación
28
Computación de Alto Rendimiento
29
Computación de Alto Rendimiento
Mejor
Balance global OK pero debido a la dependencia de tareas P4 está ocioso
30
Computación de Alto Rendimiento
Para Equilibrado de Carga
Las técnicas de
mapeo estático
distribuyen las tareas
entre los procesos
antes de la ejecución
del algoritmo.
31
Computación de Alto Rendimiento
Dividir en bloques por sumas, columnas, submatrices, etc
La matriz se particiona
en bloques de
dimensión n/p1 * n/p2
32
Computación de Alto Rendimiento
Ejercicio
33
Computación de Alto Rendimiento
Cantidad de datos a
compartir en una
multiplicación de matrices
con una partición
unidimensional y
bidimensional de
la matriz de salida.
34
Computación de Alto Rendimiento
35
Computación de Alto Rendimiento
36
Computación de Alto Rendimiento
37
Computación de Alto Rendimiento
38
Computación de Alto Rendimiento
Mas sentido porque solo hay interaccion en la forntera
entre 2 colores, solo para las tareas de la frontera, por
ejemplo tarea roja y tarea naranja nunca se van a
comunicar. Menor numero de comunicaciones
39
Computación de Alto Rendimiento
40
Computación de Alto Rendimiento
41
Computación de Alto Rendimiento
Ejercicios
42
Computación de Alto Rendimiento
