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 anterior | Volver al principio del trabajo | Página siguiente  |