Índice 1. Introducción. 2. Análisis de
algoritmos. 3. Metodología de desarrollo de programas
paralelos. 4. Esquemas de algoritmos paralelos. 5. Problemas
numéricos. Librerías.
? Los problemas que pueden resolverse mediante un algoritmo
paralelo son, obviamente, muy heterogéneos. Suelen ser
problemas de complejidad elevada, aún no perteneciendo al
grupo de problemas intratables (el número de operaciones
crece de forma rápida –p.e. exponencial– con
el tamaño del problema).
? Dentro del conjunto de problemas tratables (el número de
operaciones crece polinómicamente con el tamaño del
problema) se suelen dar dos situaciones que hacen necesaria la
programación paralela: – Problemas de gran
dimensión – Problemas de tiempo real Otro tipo de
problemas: problemas de gran desafío, por su relevancia
social (genoma humano, meteorología, clima,
fenómenos sísmicos…).
? Diferentes modelos sobre distintos aspectos de la
programación paralela: – Modelo arquitectónico:
arquitectura de la máquina — multiprocesadores: memoria
compartida — multicomputadores: paso de mensajes — modelos
mixtos – Modelo de programación: herramientas de alto
nivel (OpenMP, MPI). – Modelo de coste: permite evaluar el coste
del algoritmo.
Índice 1. Introducción. 2. Análisis de
algoritmos. 3. Metodología de desarrollo de programas
paralelos. 4. Esquemas de algoritmos paralelos. 5. Problemas
numéricos. Librerías.
? En la programación paralela (al igual que en la
secuencial) son necesarias herramientas que permitan estimar el
tiempo de ejecución y la memoria consumidos por un
algoritmo, para determinar si es adecuado o no para la
resolución del problema. El objetivo es desarrollar
algoritmos eficientes (eficiencia: relación entre los
recursos que consume y los resultados que obtiene).
? Factores que influyen en el tiempo de ejecución de un
programa: – el lenguaje de programación (el programador) –
la máquina – el compilador (opciones) – los tipos de datos
– los usuarios que estén trabajando en el sistema
? Factores que influyen en el tiempo de ejecución de un
programa paralelo: – la competencia por la memoria (bloques de
cache) – la fracción de código secuencial (Amdahl)
– la creación/asignación de procesos – la
computación extra: variables de control,
identificación de procesos, cálculos
adicionales… – la comunicación (para memoria
distribuida) – la sincronización – los desequilibrios de
carga
? Estudio del algoritmo a priori Antes de hacer el programa
correspondiente. Sirve para identificar si el algoritmo es
adecuado para el problema, o para seleccionar entre varios
algoritmos. También sirve para determinar el tamaño
de los problemas a resolver en función de las limitaciones
de tiempo y memoria.
? Estudio a posteriori Tras haber hecho el programa. Sirve para
comparar entre dos programas según el tamaño de
entrada. También para encontrar fallos o posibles mejoras
de un programa. ? Estudio teórico (a priori o posteriori)
y estudio experimental (a posteriori).
? Tipos de estudios teóricos: Tiempo de ejecución
(ej. ordenación) – caso más favorable, cota
inferior: tm (n) – caso más desfavorable, cota superior:
tM (n) – caso promedio: tp (n) donde: n es el tamaño de la
entrada ? es una entrada de las S posibles entradas
? Tipos de estudios teóricos: Ocupación de memoria
– caso más favorable, cota inferior: mm (n) – caso
más desfavorable, cota superior: mM (n) – caso promedio:
mp (n) donde: n es el tamaño de la entrada ? es una
entrada de las S posibles entradas
? Conteo de instrucciones – decidir qué
instrucciones/operaciones (flop) se quieren contar. – asignar
costes a instrucciones de cada tipo. – una función: coste
de las instrucciones que la componen. – bucles: mediante
sumatorios o cotas superior e inferior si no se conoce el
número de veces que se ejecutará. – bifurcaciones:
contar el número de veces que pasa por cada rama, o
establecer una cota superior (rama más costosa) o una
inferior (rama menos costosa).
? Conteo de instrucciones (caso promedio) k número de
instrucciones del programa tp (n,i) número promedio de
veces que la instrucción i se ejecuta para una entrada de
tamaño n (Gp:) p (i,j) probabilidad de que la
instrucción i se ejecute j veces
? Notación asintótica Dado que lo que interesa es
saber cómo se comporta el algoritmo cuando crece el
tamaño de la entrada (tamaños grandes), ya que es
cuando podemos tener problemas de tiempo, se suelen utilizar
notaciones asintóticas. Acotan la forma en que crece el
tiempo de ejecución cuando el tamaño de la entrada
tiende a infinito, sin tener en cuenta las constantes que le
afectan.
? Acotar superiormente, orden de f: ? Acotar inferiormente, omega
de f: ? Acotar sup. e inferiormente, orden exacto de f:
? A nivel práctico, a veces interesa no perder la
información de las constantes del término de mayor
orden: (Gp:) ? Algunas relaciones entre órdenes:
? Factores que afectan al tiempo de ejecución de un
programa paralelo: (Gp:) Estimación del tiempo de
ejecución real (Gp:) Conteo de instrucciones (Gp:)
¿?
? Tiempo de comunicación punto a punto entre dos
procesadores: (Gp:) ? Tiempo de comunicación de un mensaje
dividido en paquetes a distancia d: ? En general, conviene
agrupar mensajes (full duplex?, red conmutada?,
Ethernet…)
? Ejemplo: suma de n números s = a[0]; for(i=1; i < n;
i++) s = s + a[i]; ? Tiempos de la versión secuencial: –
conteo de instrucciones: t(n) = tcalc(n) = 2n – 1 – conteo de
operaciones: t(n) = tcalc(n) = n – 1
? Ejemplo: suma de n números (memoria compartida) – una
versión paralela con n/2 procesos doall pid = 0, n/2-1 {
ini = 2 * pid; des = 1; act = true; for (k=1; k++; k <= log n)
{ if (act) { a[ini] = a[ini] + a[ini+des]; des = des * 2; } if
((i mod des)!=0) act = false; } }
? Ejemplo: suma de n números (memoria compartida) – una
versión paralela con n/2 procesos (memoria compartida):
(Gp:) 0 (Gp:) 1 (Gp:) 2 (Gp:) 3 (Gp:) 4 (Gp:) 5 (Gp:) 6 (Gp:) 7
(Gp:) k = 1 (Gp:) 0, 1 (Gp:) 2, 3 (Gp:) 4, 5 (Gp:) 6, 7 (Gp:) k =
2 (Gp:) 0, 1, 2, 3, 4, 5, 6, 7 (Gp:) k = log n (Gp:) 0, 1, 2, 3
(Gp:) 4, 5, 6, 7 (Gp:) …
? Ejemplo: suma de n números (memoria compartida) ?
Problemas: – distribución del trabajo entre procesos –
overheads = variables auxiliares, comprobaciones… – ley de
Amdahl ? Tiempos de la versión paralela (mem. compartida):
– conteo de instrucciones: tcalc(n, n/2) = 3 + 6 log n – conteo
de operaciones: tcalc(n, n/2) = log n (+ sincronización
tras cada iteración)
? Ejemplo: suma de n números (memoria distribuida) – una
versión paralela con n/2 procesos doall Pi, i = 0, n/2-1 {
des = 1; act = true; for (k=1; k++; k <= log n -1) { if (act)
{ a = a + b; des = des * 2; if ((i mod des)!=0) { act = false;
Envia (a, Pi-des/2); } else Recibe (b, Pi+des/2); } } if (i = 0)
a = a + b; }
? Ejemplo: suma de n números (mem. distribuida) ?
Problemas: – añade la comunicación y su
gestión, cuyo coste puede influir más o menos ?
Tiempos de la versión paralela (mem. distribuida): –
instrucciones: tcalc(n, n/2) = 4+6 (log n -1) – operaciones:
tcalc(n, n/2) = log n – comunicación: tcom(n, n/2) = (log
n -1) (ts + tw) (suponiendo comunicaciones directas y en
paralelo)
? Ejemplo: suma de n números (mem. distribuida) speed-up
para n=64 y p=32 según relación entre ts, tw y
top
? Algunas conclusiones: – No tiene sentido suponer p ilimitado
para una entrada constante (eliminar la restricción n =
2p), n y p deben ser independientes. – No tiene sentido utilizar
programación paralela para resolver problemas
pequeños. Mejor resolverlos secuencialmente. En el
ejemplo, el coste es lineal, y, por tanto, no es adecuado. –
Dependiendo de la plataforma, un programa derivado de un
algoritmo puede proporcionar unas prestaciones muy
diferentes.
? Medidas de prestaciones: – Speed-up ? Ejemplo: suma de n
números (instr./flops) – Memoria compartida – Memoria
distribuida
(Gp:) ? Ejemplo: suma de n números (flops) – Memoria
compartida – Memoria distribuida ? Medidas de prestaciones: –
Eficiencia
? Medidas de prestaciones: – Coste – Función overhead:
(Gp:) ? Ejemplo: suma de n números (flops) – Memoria
compartida – Memoria distribuida
? Escalabilidad Que se mantengan las prestaciones al aumentar p y
el tamaño del problema. (Gp:) ? Función de
isoeficiencia Indica la forma en la que debe aumentar el
tamaño de la entrada en función del tamaño
del sistema para mantener las prestaciones (despejar n en
función de p).
? Ejemplo: suma de n números (flops) Memoria compartida –
manteniendo proporcional el coste del secuencial a la
función overhead: – comparando los términos de
mayor orden: I(p) = p log p Memoria distribuida – manteniendo
proporcional el coste del secuencial a la función
overhead: – comparando los términos de mayor orden: I(p) =
p log p
? Ejemplo: suma de n números (flops) – en ambos casos I(p)
= p log p
Índice 1. Introducción. 2. Análisis de
algoritmos. 3. Metodología de desarrollo de programas
paralelos. 4. Esquemas de algoritmos paralelos. 5. Problemas
numéricos. Librerías.
? Es diferente paralelizar un algoritmo o programa secuencial,
que programar en paralelo una aplicación desde el
comienzo. ? En el primer caso, interesa detectar aquellas partes
del código con un mayor coste computacional. Lo más
habitual es utilizar trazas, timers, profiling, etc., y ejecutar
en paralelo aquellas partes que ofrecen un buen rendimiento (por
ejemplo, paralelismo incremental de OpenMP).
? En el segundo caso, se empieza analizando las
carac-terísticas de la propia aplicación, para
determinar el/los algoritmos paralelos más adecuados. OJO:
conviene partir de un buen algoritmo ya optimizado (¡no hay
que reinventar la rueda!). ? Aunque no hay un “camino
único”, se suele recomendar utilizar un determinado
procedimiento o metodología.
? La programación paralela añade, respecto a la
programación secuencial, una serie de aspectos a tener en
cuenta: – Concurrencia (sincronización,
comunicación). – Asignación de datos y
código a procesadores. – Acceso simultáneo a datos
compartidos (sincronización). – Escalabilidad.
? Otra diferencia entre la programación secuencial y la
paralela es la forma en que los módulos que componen una
aplicación se pueden ensamblar: – Composición
secuencial: los módulos se ejecutan secuencialmente. –
Composición paralela: diferentes módulos se
ejecutan simultáneamente sobre conjuntos disjuntos de
procesos (escalabilidad y localidad). – Composición
concurrente: diferentes módulos se ejecutan
concurrentemente sobre los mismos procesos (solapamiento
computación y comunicación).
(Gp:) PROBLEMA (Gp:) Particionado (Gp:) Comunicación (Gp:)
Aglomerado (Gp:) Mapeado Modelo PCAM
ESTA PRESENTACIÓN CONTIENE MAS DIAPOSITIVAS DISPONIBLES EN
LA VERSIÓN DE DESCARGA