Í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