13 Metodología de Diseño de Foster De "Designing and Building Parallel Programs" por Ian Foster Cuatro pasos: Particionar Dividir cómputo y datos Comunicación Intercambio de datos entre cómputos Aglomeración Agrupar tareas para mejorar rendimiento Mapeo Asignar tareas a procesadores/hilos
14 Diseñando programas paralelos Particionar Divide el problema en tareas Comunicar Determina la cantidad y el patrón de comunicación Aglomerar Combinar tareas Mapear Asignar tareas aglomeradas a los hilos generados (Gp:) Problema
(Gp:) Tareas iniciales
(Gp:) Comunicación
(Gp:) Tareas combinadas
Programa final
15 Modelos de Programación Paralela Descomposición funcional Paralelismo de tareas Dividir el cómputo, asociarle datos Tareas independientes del mismo problema Descomposición de datos La misma operación ejecutando diferentes datos Dividir datos en piezas, asociarles cómputo
16 Métodos de descomposición Descomposición funcional Enfocarse a cómputo puede revelar la estructura en un problema (Gp:) Grid reprinted with permission of Dr. Phu V. Luong, Coastal and Hydraulics Laboratory, ERDC
Descomposición por dominio Enfocarse en la estructura de datos más grande o más frecuentemente accesada Paralelismo en los datos La misma operación aplicada a todos los datos (Gp:) Modelo atmosférico (Gp:) Modelo Oceano (Gp:) Modelo terrestre (Gp:) Modelo de hidrología
17 Descomposición en Pipeline La computación se hace en etapas independientes Descomposición funcional Los hilos se asignan a una etapa a computar Línea de ensamble de automóviles Descomposición de datos Los hilos procesan todas las etapas de una sola instancia Un trabajador construye un auto completito
18 Ejemplo de LAME Encoder LAME MP3 encoder Proyecto Open source Herramienta educativa El objetivo de este proyecto es Mejorar la calidad Mejorar la velocidad de la codificación a MP3
19 Estrategia de LAME Pipeline (Gp:) Frame N (Gp:) Frame N + 1 (Gp:) Tiempo (Gp:) Otro N (Gp:) Preludio N (Gp:) Acústicos N (Gp:) Codificación N (Gp:) T 2 (Gp:) T 1 (Gp:) Acústicos N+1 (Gp:) Preludio N+1 (Gp:) Otro N+1 (Gp:) Codificación N+1 (Gp:) Acústicos N+2 (Gp:) Preludio N+2 (Gp:) T 3 (Gp:) T 4 (Gp:) Preludio N+3 (Gp:) Barrera Jerárquica
Otro Preludio Acústicos Codificación Frame (Gp:) Extraer siguiente frame Caracterización del frame Poner parámetros del encoder
(Gp:) Analisis FFT long/short Ensamblar el filtro
(Gp:) Aplicar filtros Suprimir ruidos Cuantiza y cuenta bits
(Gp:) Agregar encabezado del frame Verificar si es correcto Escribe al disco
20 Diseño ¿Cuál es el beneficio esperado?
¿Cómo logramos esto con el menor esfuerzo?
¿Cuánto se lleva paralelizar? ¿Cuánto esfuerzo se requiere para rediseñar? Prototipo rápido con OpenMP Aceleración(2P) = 100/(96/2+4) = ~1.92X
21 OpenMP Paralelismo Fork-join: El hilo maestro se divide en un grupo de hilos como sea necesario El paralelismo va incrementando Un programa secuencial evoluciona a un programa paralelo (Gp:) Regiones Paralelas (Gp:) Hilo maestro
22 Diseño #pragma omp parallel for for( int i = start; i < = end; i+= 2 ){ if( TestForPrime(i) ) globalPrimes[gPrimesFound++] = i; ShowProgress(i, range); }
(Gp:) OpenMP
(Gp:) Crea hilos aquí para Esta región paralela
(Gp:) Divide iteraciones de el ciclo for
23 Actividad 3 Ejecuta la versión OpenMP del código Localiza el directorio PrimeOpenMP y la solución Compila el código Ejecuta con '1 5000000' para comparar ¿Cuál es la aceleración?
24 Diseño ¿Cuál es el beneficio esperado? ¿Cómo logras esto con el menor esfuerzo?
¿Cuánto tiempo se llevó paralelizar? ¿Cuánto esfuerzo se requiere para rediseñar? ¿Es la mejor aceleración posible? Aceleración de 1.40X (menor que 1.92X)
25 Depuración ¿Es la implementación correcta de paralelismo? No! Los resultados son diferentes cada ejecución .
26 Depuración Intel® Parallel Inspector indica errores notorios en la paralelizacion como condiciones de concurso e interbloqueos Análisis de errores en la paralelización Intel® Parallel Inspector Dónde están los Interbloqueos o Condiciones de Concurso Colector De Datos en tiempo de ejecución
27 Intel® Parallel Inspector (Errores en la Paralelización) Seleccionar información en relación con condiciones de concurso e interbloqueos Ver la descripción general de errores de la paralelización (Ti3) Selecciona el error e inspecciona el código
28 Actividad 4 Usa Parallel Inspector para analizar la aplicación paralelizada Usa Intel Parallel Inspector para encontrar la condición de concurso que hace que el cálculo de números primos sea incorrecto Ejecuta la aplicación ¿Se reportan errores?
29 Depuración ¿Cuánto esfuerzo de requiere para rediseñar?
¿Cuánto nos llevará paralelizar?
Parallel Inspector solo reportó 3 dependencias, por lo tanto no hay mayores compliaciones
30 Depuración #pragma omp parallel for for( int i = start; i < = end; i+= 2 ){ if( TestForPrime(i) ) #pragma omp critical globalPrimes[gPrimesFound++] = i; ShowProgress(i, range); }
#pragma omp critical { gProgress++; percentDone = (int)(gProgress/range *200.0f+0.5f) } (Gp:) Creará una sección crítica para esta referencia
(Gp:) Creará una sección crítica para ambas referencias
31 Actividad 5 Modifica y ejecuta la versión de Open MP del código Añade pragmas de regiones críticas al código Compila el código Ejecuta Parallel Inspector (Errores de Paralelización) Si los errores siguen presentes, haz las correcciones apropiadas al código y ejecuta de nuevo en Parallel Inspector
Ejecuta con '1 5000000' para comparar Compila y ejecuta sin debugging ¿Cuál es la aceleración?
32 Depuración Respuesta correcta, pero el rendimiento bajo al ~1.33X
¿Es lo mejor que podemos esperar de este algoritmo? No! De acuerdo a la Ley de Amdahl, podemos esperar una aceleración cerca de 1.9X
33 Problemas comunes de rendimiento Sobrecarga en paralelo Dada por la creación de hilos, planificación. Sincronización Datos globales excesivos, contención de los mismos objetos de sincronización Carga desbalanceada Distribución no adecuada del trabajo en paralelo Granularidad No hay suficiente trabajo paralelo
34 Afinando para mejorar el rendimiento Parallel Amplifier (Locks y Waits) apunta a cuellos de botella en el rendimiento en aplicaciones con hilos (Gp:) Locks & Waits (Gp:) Intel® Parallel Amplifier
35 Parallel Amplifier/ Locks y Waits La gráfica muestra una porción de tiempo significativa en condición ociosa como resultado de la sección crítica FindPrimes() y ShowProgress() están significativamente impactadas por el tiempo ocioso ocurriendo en la sección crítica
36 Parallel Amplifier/ Locks y Waits ShowProgress() consume 558/657 (85%) del tiempo permaneciendo ocioso en una sección crítica Haz Double Click en ShowProgress() en la sección crítica más larga para ver el código fuente
37 Parallel Amplifier/ Resumen El tiempo transcurrido muestra .571 sec Tiempo de espera/ Núcleos = 1.87/4 =.47 sec Esperando el 82% del tiempo transcurrido en una sección crítica La mayoría del tiempo 1 núcleo y ocasionalmente están ocupados 2
38 Parallel Amplifier/ Concurrencia Concurrencia (Function -Caller Function Tree) ShowProgress es llamada de FindPrimes y representa mayormente la razón por la cual la concurrencia es pobre
39 Parallel Amplifier/ Concurrencia Concurrencia (Thread -Function -Caller Function Tree) Esta pantalla muestra como cada hilo contribuye al problema de concurrencia Expandiendo cualquier hilo las funciones que más contibuyen
40 Rendimiento Double Click en ShowProgress en la segunda sección crítica más larga Esta implementación tiene llamadas de sincronización implícita – printf Esto limita la mejora del rendimiento debido a cambios de contexto resultantes De regreso a la etapa de diseño
41 Actividad 6 Usar Parallel Amplifier para analizar la aplicación con hilos Usar la herramienta Parallel Amplifier (Análisis de Locks y Waits) Identifica los waits y locks que más contribuyen
42 Rendimiento ¿Es esto mucha contención esperada?
El algoritmo tiene muchas más actualizaciones a variables que las 10 necesitadas para mostrar el progreso void ShowProgress( int val, int range ) { int percentDone; gProgress++; percentDone = (int)((float)gProgress/(float)range*200.0f+0.5f);
if( percentDone % 10 == 0 ) printf("bbbb%3d%%", percentDone); } void ShowProgress( int val, int range ) { int percentDone; static int lastPercentDone = 0; #pragma omp critical { gProgress++; percentDone = (int)((float)gProgress/(float)range*200.0f+0.5f); } if( percentDone % 10 == 0 && lastPercentDone < percentDone / 10){ printf("bbbb%3d%%", percentDone); lastPercentDone++; } } Este cambio debe arreglar el problema de contención
43 Diseño Meta Elimina la contención debido a la sincronización implícita ¡La aceleración es 2.32X ! ¿Es correcto?
44 Rendimiento Nuestra medida base original tenía la actualización del algoritmo de progreso "defectuoso"
¿Es lo mejor que podemos esperar de este algoritmo?
¡La aceleración actual es 1.40X (< < 1.9X)!
45 Actividad 7 Modifica la función ShowProgress (en la versiones serial y OpenMP) para solo mostrar la salida necesaria
Recompila y ejecuta el programa Asegurarse que no se están usando banderas de instrumentación
¿Cuál es la aceleración con respecto a la versión serial? if( percentDone % 10 == 0 && lastPercentDone < percentDone){ printf("bbbb%3d%%", percentDone); lastPercentDone += 10; }
46 Revisando el Rendimiento Locks y Waits – Antes y Después de cambiar a la función printf En la versión más rápida – el printf es llamado ~ 10x menos veces – lastPercentDone < percentDone / 10 Locks y Waits "self wait count" y "poor" muestran una diferencia significativa entre versiones
47 Revisando el Rendimiento Veamos los Locks de OpenMP. void FindPrimes(int start, int end) { // start is always odd int range = end – start + 1;
#pragma omp parallel for for( int i = start; i < = end; i += 2 ) { if( TestForPrime(i) ) #pragma omp critical globalPrimes[gPrimesFound++] = i;
ShowProgress(i, range); } } (Gp:) Hay un lock en un ciclo
void FindPrimes(int start, int end) { // start is always odd int range = end – start + 1;
#pragma omp parallel for for( int i = start; i < = end; i += 2 ) { if( TestForPrime(i) ) globalPrimes[InterlockedIncrement(&gPrimesFound)] = i;
ShowProgress(i, range); } }
48 Revisando el Rendimiento Veamos el segundo lock
void ShowProgress( int val, int range ) { int percentDone; static int lastPercentDone = 0;
#pragma omp critical { gProgress++; percentDone = (int)((float)gProgress/(float)range*200.0f+0.5f); } if( percentDone % 10 == 0 && lastPercentDone < percentDone / 10){ printf("bbbb%3d%%", percentDone); lastPercentDone++; } } (Gp:) Este es un lock que está siendo llamado dentro de un ciclo
void ShowProgress( int val, int range ) { long percentDone, localProgress; static int lastPercentDone = 0;
localProgress = InterlockedIncrement(&gProgress); percentDone = (int)((float)localProgress/(float)range*200.0f+0.5f);
if( percentDone % 10 == 0 && lastPercentDone < percentDone / 10){ printf("bbbb%3d%%", percentDone); lastPercentDone++; } }
49 Actividad 8 Modifica las regiones críticas de OpenMP para usar InterlockedIncrement en vez de Re-compila y ejecuta el programa
´¿Cuál es la aceleración con respecto a la versión serial?
50 Análisis del balanceo de carga Usa el análisis de concurrencia de Parallel Amplifier Selecciona "Thread -Function -Caller Function Tree" Observa que los 4 hilos hacen cantidades de trabajo desiguales
51 Arreglando el Desbalanceo de Carga Distribuye el trabajo de manera más uniforme (Gp:) void FindPrimes(int start, int end) { // start is always odd int range = end – start + 1;
#pragma omp parallel for schedule(static,8) for( int i = start; i < = end; i += 2 ) { if( TestForPrime(i) ) globalPrimes[InterlockedIncrement(&gPrimesFound)] = i; ShowProgress(i, range); } }
La aceleración lograda es 1.68X
52 Modifica el código para un mejor balanceo de carga Añade la cláusula schedule (static, 8) al pragma de OpenMP parallel for Re-compila y ejecuta el programa
¿Cuál es la aceleración comparada con la versión serial? Actividad 9
53 Análisis final de balanceo de carga La aceleración lograda es 1.80X
54 Análisis Comparativo Paralelizar aplicaciones requiere varias iteraciones a través del ciclo de desarrollo de software
55 Metodología de paralelización Lo que se Cubrió Cuatro pasos del ciclo de desarrollo para escribir aplicaciones paralelas desde el código serial y las herramientas de Intel® para soportar cada paso Análisis Diseño (Introducir Hilos) Depurar para la correctud Afinar el rendimiento Las aplicaciones paralelas requieren múltiples iteraciones de diseño, depuración y afinación de rendimiento Usar las herramientas para mejorar productividad
| Página siguiente |