Vista previa del material en texto
Resolución de problemas en paralelo Algoritmos Paralelos Tema 1. Introducción a la computación paralela (segunda parte) Vicente Cerverón – Universitat de València Introducción a la Computación Paralela 34 Descomposición de problemas • El primer paso para diseñar un algoritmo paralelo es descomponer el problema en problemas más pequeños. Estos subproblemas son asignados a procesadores para ser resueltos simultáneamente. Básicamente hay dos tipos de descomposición 1. Descomposición de dominio 2. Descomposición funcional Resolución de problemas en paralelo Introducción a la Computación Paralela 35 • En la descomposición de dominio, también llamada paralelismo de datos, los datos son divididos en partes de aproximadamente el mismo tamaño y las partes son asignadas a diferentes procesadores. Cada procesador trabaja sólo com la parte de datos que le son asignados. Por supuesto, los procesadores pueden necesitar comunicarse para intercambiar datos. • El paralelismo de datos permite mantener un flujo único de control y seguir el modelo SPMD (single program multiple data). El algoritmo con paralelismo de datos consiste en una secuencia de instrucciones aplicadas a distintos datos. Descomposición de dominio Introducción a la Computación Paralela 36 • La estrategia de descomposición de dominio puede no ser la más eficiente cuando las partes asignadas a los diferentes procesadores pueden requerir tiempos de proceso significativamente diferentes de unos a otros, sin que dichas diferencias puedan ser conocidas previamente. En tal caso el tiempo de ejecución viene determinado por el proceso que tarde más, mientras que los otros procesadores permanecen ociosos un tiempo. • La descomposición funcional o paralelismo de tareas (también reparto dinámico de tareas) el problema se divide en un gran número de partes más pequeñas (muchas más partes que procesadores disponibles) y las subtareas son asignadas a los procesadores disponibles. Tan pronto como un procesador termina una subtarea, recibe otra subtarea hasta que queden resueltas todas. • El paralelismo de tareas se implementa sobre un paradigma de maestro y esclavos. El proceso maestro va asignando las subtareas a los procesos esclavos, recogiendo los resultados producidos y asignando subtareas restantes. Descomposición funcional Introducción a la Computación Paralela 37 Los paradigmas de programación no están unívocamente ligados a las arquitecturas paralelas, aunque sí que guarden relación como se indicará, existen dos paradigmas principales de programar computadores paralelos: • Programación paralela mediante memoria compartida (espacio de direcciones único) • Programación paralela mediante paso de mensajes Paradigmas de programación paralela Introducción a la Computación Paralela 38 • El programador escribe el programa, bien empleando directivas de paralelismo de datos bien asumiendo explícitamente diferentes procesos que pueden acceder a un espacio de direcciones único, con variables globales compartidas. • Este paradigma es apropiado para arquitecturas de memoria compartida, aunque el espacio de direcciones único también puede ser simulado sobre arquitecturas de memoria distribuida. Programación paralela mediante Programación paralela mediante Programación paralela mediante Programación paralela mediante memoria compartidamemoria compartidamemoria compartidamemoria compartida Introducción a la Computación Paralela 39 • El programador explícitamente divide el trabajo y los datos entre varios procesos y debe gestionar la comunicación de datos entre ellos. • Esta aproximación es completamente flexible, si bien requiere un mayor trabajo del programador. Puede ser empleado en arquitecturas de memoria distribuida e incluso en redes de ordenadores, y también en arquitecturas de memoria compartida, aunque en ese caso los diferentes procesos utilizan partes de memoria independientes y separadas. Programación paralela mediante Programación paralela mediante Programación paralela mediante Programación paralela mediante paso de mensajespaso de mensajespaso de mensajespaso de mensajes Introducción a la Computación Paralela 40 Métricas • Concurrencia • Tiempo de ejecución paralelo • Coste paralelo • Trabajo • Aceleración • Eficiencia Análisis de algoritmos paralelos Conceptos • Optimalidad • Granularidad • Sobrecostes • Ley de Amdahl • Ley de Gustaffon Introducción a la Computación Paralela 41 Aceleración (speed-up) donde ts es el tiempo de ejecución en un procesador secuencial y tp es el tiempo de ejecución en un computador paralelo. Debe usarse el tiempo del mejor algoritmo secuencial conocido. El algoritmo para la implementación paralela puede ser diferente. Puede usarse el tiempo (real) o el estimado por número de pasos Análisis de algoritmos paralelos S(p) = Execution time using one processor (best sequential algorithm) Execution time using a multiprocessor with p processors ts tp = Introducción a la Computación Paralela 42 Aceleración máxima La aceleración máxima es usualmente p con p procesadores (aceleración lineal). Es posible tener aceleración superlineal (mayor que p) pero sólo en casos específicos debidos: • Mayor disponibilidad de memoria principal • Algoritmos no deterministas Análisis de algoritmos paralelos Introducción a la Computación Paralela 43 Aceleración según la ley de Amdahl Análisis de algoritmos paralelos Serial section Parallelizable sections (a) One processor (b) Multiple processors fts (1 - f)ts ts (1 - f)ts /ptp p processors Introducción a la Computación Paralela 44 Análisis de algoritmos paralelos Aceleración según la ley de Amdahl S(p) = ts p = fts + (1 − f )ts /p 1 + (p − 1)f 4 8 12 16 20 4 8 12 16 20 f = 20% f = 10% f = 5% f = 0% Number of processors, p Introducción a la Computación Paralela 45 El principal objetivo cuando se diseña un algoritmo paralelo y se escribe un programa paralelo es conseguir mejores prestaciones que una versión secuencial. Para ello hay que tener varios aspectos en consideración: • equilibrado de la carga • minimización de las comunicaciones • solapamiento de computación y comunicaciones Aspectos de programación paralela Introducción a la Computación Paralela 46 Equilibrado de la carga El equilibrado de la carga es la labor de dividir equitativamente el trabajo entre los procesadores disponibles. Puede ser inmediato cuando el coste de las operaciones es el mismo para cada dato, en cuyo caso se procede a un simple paralelismo de datos, o no tanto cuando el tiempo de proceso depende de los valores de los datos. Aspectos de programación paralela Introducción a la Computación Paralela 47 Minimización de las comunicaciones El tiempo total para completar la ejecución es la preocupación principal de la programación paralela, y en él intervienen tres componentes: * tiempo de computación * tiempo ocioso (idle time) * tiempo de comunicación Aspectos de programación paralela Introducción a la Computación Paralela 48 Minimización de las comunicaciones El tiempo de computación es el tiempo empleado en realizar cálculos sobre los datos. Idealmente, esperaríamos que al disponer de P procesadores trabajando sobre un problema pudiésemos terminar el trabajo en una fracción de 1/P del tiempo empleado en un procesador secuencial. Este sería el caso si todo el tiempo de todos los procesadores pudiera ser empleado en realizar cálculos. El tiempo ocioso (idle time) es el tiempo que un procesador gasta esperando datos de otros procesadores. Durante este tiempo el procesador no realiza trabajo útil. También existen tiempos ociosos cuando determinada subsecuencia del problema no puede ser dividida entre los procesadores disponibles y sólo puede ser realizada por un procesador o un subconjunto de ellos. El tiempo de comunicación es el tiempo empleado en enviar y recibir datos en forma de mensajes. El coste de las comunicaciones enel tiempo total de ejecución puede ser expresado en términos de latencia y ancho de banda, siendo la latencia el tiempo necesario para preparar el envío de cada mensaje y el ancho de banda la velocidad de transmisión por dato de los que forman el mensaje. Los programas secuenciales no emplean comunicaciones entre procesos, por lo que debe minimizarse siempre el tiempo de comunicaciones que supone en todo caso un sobrecoste. Aspectos de programación paralela Introducción a la Computación Paralela 49 Solapamiento de computación y comunicaciones Siempre que sea posible, deben evitarse los tiempos ociosos, procurando que los procesadores realicen cálculos útiles mientras esperan datos necesarios provenientes de otros procesadores. Esto, que se puede conseguir mediante métodos de comunicación no bloqueantes, es siempre difícil y no existen modos generales de conseguirlo, diseñándose en cada caso para cada algoritmo. Aspectos de programación paralela Introducción a la Computación Paralela 50 • Emplearemos pseudocódigo para describir los algoritmos paralelos para poder analizarlos, como paso previo a su programación • El pseudocódigo será sencillo, pero a la vez parecido a los lenguajes y estructuras que se usarán en la programación (codificación) paralela • Existirán dos maneras de emplear pseudocódigo, según sea: – para memoria compartida (espacio de direcciones único) – para paso de mensajes • Lo ejemplificamos con el problema de sumar con P proceos los N elementos de un vector Descripción de algoritmos en pseudocódigo Introducción a la Computación Paralela 51 • Para el paradigma de memoria compartida (1) Pk (programa que ejecutará el proceso k, siendo k de 0 a P-1) variables globales v[N], suma, sumaparcial[P] inicio sumaparcial[k] = v[k*N/P] desde i=1 hasta N/P-1 con i++ sumaparcial[k] = sumaparcial[k] + v[k*N/P + i] (sigue …) Descripción de algoritmos en pseudocódigo Introducción a la Computación Paralela 52 • Para el paradigma de memoria compartida (2) (continuación …) desde salto=1 hasta P/2 con salto*=2 si k MOD 2*salto == 0 sumaparcial[k] = sumaparcial[k] + sumaparcial[k + salto] si k==0 suma = sumaparcial[0] fin Descripción de algoritmos en pseudocódigo Introducción a la Computación Paralela 53 • Para el paradigma de paso de mensajes (1) Pk (programa que ejecutará el proceso k, siendo k de 0 a P-1) variables v[N/P], suma, aux inicio suma = v[0] desde i=1 hasta N/P-1 con i++ suma = suma + v[i] (sigue …) Descripción de algoritmos en pseudocódigo Introducción a la Computación Paralela 54 • Para el paradigma de paso de mensajes (2) (continuación …) desde salto=1 hasta P/2 con salto*=2 si k MOD 2*salto == 0 recibir(k+salto, REF aux) suma = suma + aux si_no si k MOD salto == 0 enviar(k-salto, suma) fin En este caso la súma total sólo la sabrá el P0 Descripción de algoritmos en pseudocódigo Introducción a la Computación Paralela 55 • Ejercicio: resolver la suma mediante paso de mensajes para que todos los procesos acaben conociendo la suma total • Ejercicio: resolver mediante los dos paradigmas de programación paralela el problema de normalizar un vector, esto es, dividir cada uno de sus componentes por su módulo (la raíz cuadrada de la suma de los cuadrados de cada elemento) Fin del tema 1 Descripción de algoritmos en pseudocódigo
