9 Encontrando Concurrencia del Diseño del Espacio Descomposición de tareas Análisis de descomposición Descomposición de dominios Ordenar grupos Compartir datos Análisis de dependencias Agrupar tareas
10 Encontrando concurrencia Del código serial: Usa un analizador, tal como “Intel® VTuneTM Performance Analyzer” Identifica hotspots en una aplicación Examina el código en los hotspots Determina cuando las tareas dentro de los hotspots pueden ejecutarse independientemente De un documento de diseño: Examina los componentes de diseño Encuentra componentes que contienen operaciones independientes
11 Espacio de Diseño de la Estructura del Algoritmo Estructura usada para organizar computo para soportar paralelismo (Gp:) Pipeline
(Gp:) Organizado por flujo de datos
(Gp:) ¿Lineal?
(Gp:) ¿Recursivo?
(Gp:) Organizado por tareas
(Gp:) ¿Lineal?
(Gp:) ¿Recursivo?
(Gp:) Organizado por datos
(Gp:) Datos Recursivos
(Gp:) ¿Regular?
(Gp:) ¿Irregular?
(Gp:) Paralelismo de tareas
(Gp:) Descomposición Geométrica
(Gp:) Divide y Vencerás
(Gp:) Coordinación basada en eventos
¿Cómo está estructurado el cómputo?
12 Consideraciones que afectan a las estructuras de los algoritmos Las siguientes consideraciones afectan las metas de diseño, Eficiencia El programa paralelo debe ejecutarse rápidamente y hacer buen uso de los recursos de procesamiento Simplicidad Algoritmos simples (fáciles de entender) son más fáciles de desarrollar, depurar, verificar y mantener Portabilidad Los programas deben ejecutarse en el rango más amplio de computadoras paralelas Escalabilidad Los algoritmos paralelos deben ser efectivos en un amplio rango de número de hilos y núcleos, y tamáños de datos o conjuntos de datos
13 Consideraciones que afectan a las estructuras de los algoritmos Puede haber conflictos entre dos o más de las consideraciones (Eficiencia, Simplicidad, Portabilidad, Escalabilidad) El balanceo de las consideraciones es crítico para obtener el mejor código paralelo
14 Estructuras de Soporte del Espacio de Diseño Bloques de construcción de alto nivel usados para organizar el código fuente Categorizados en estructuras de programa y estructuras de datos Cola compartida Paralelismo de Ciclos Maestro/Esclavo Estructuras de Programa Estructuras de Datos Datos compartidos SPMDSingle Program Multiple Data Arreglo distribuido Fork/Join
15 Mecanismos de Implementación del Espacio de Diseño Bloques de construcción de bajo nivel implementando bloques de construcción específicos usados en cómputo paralelo No propiamente patrones de diseño; incluidos para hacer el patrón del lenguaje autónomo * UE = Unidad de Ejecución Control de Procesos Gestión del UE* Control de hilos Com. Colectiva Comunicaciones Paso de Mensajes Otras Com Exclusión Mutua Sincronización Sinc. de Memoria/Vallas Barreras
16 Agenda Patrón de estructura de lenguaje El patrón de paralelismo de tareas El patrón de descomposición geométrica Estructuras de Soporte Resumen
17 Estructuras de Algoritmos del Espacio de Diseño (Gp:) Pipeline
(Gp:) Organizado por flujo de datos
(Gp:) ¿Lineal?
(Gp:) ¿Recursivo?
(Gp:) Organizado por tareas
(Gp:) ¿Lineal?
(Gp:) ¿Recursivo?
(Gp:) Organizado por datos
(Gp:) Datos Recursivos
(Gp:) ¿Regular?
(Gp:) ¿Irregular?
(Gp:) Paralelismo de tareas
(Gp:) Descomposición Geométrica
(Gp:) Divide y Vencerás
(Gp:) Coordinación basada en eventos
¿Cómo está estructurado el cómputo?
18 Patrón de Paralelismo de Tareas Problema: ¿Cómo puedes explotar la concurrencia en términos de un conjunto de distintas tareas? Ejemplos: Ray tracing – el cómputo de cada rayo es independiente al cómputo de cualquier otro rayo Dinámica Molecular – Actualización de las fuerzas sobre los átomos es independiente; combinando todos las fuerzas de los cómputos parciales de cada hilo se hace cuando terminan todas las fuerzas son calculadas
19 Contexto del Patrón de Paralelismo de Tareas Cada algoritmo es una colección de tareas concurrentes Puede encontrarse a través de la inspección del código El factor común es descomponer la computación en una colección de tareas concurrentes Las tareas pueden ser completamente independientes Las tareas pueden tener dependencias que necesitan satisfacerse
20 Contexto del Patrón de Paralelismo de Tareas Las tareas son usualmente conocidas a principio de la computación Las tareas pueden surgir dinámicamente (por ejemplo, búsqueda en un árbol) Normalmente deben esperar a que todas las tareas terminen antes de completar el problema Puede ser capaz de terminar cuando se encuentra la solución antes de completar todas las tareas Ejemplo: Búsqueda – si el elemento se encuentra, no es necesario seguir buscando, si el elemento no estaba presente, debe terminar de la búsqueda para asegurarse
21 Consideraciones del Patrón de Paralelismo de Tareas Tamaño de Tareas Tareas pequeñas para balancear carga vs. Tareas grandes para reducir sobrecarga de planificación Administrando Dependencias Sin destruir eficiencia, simplicidad, o escalabilidad
22 Soluciones del Patrón de Paralelismo de Tareas Tres elementos de diseño clave para patrones de paralelismo de tareas
Tareas y cómo se definen Las dependencias entre las tareas Planificación de las tareas a hilos
23 Definiendo Tareas Descomponer un algoritmo serial con descomposición de tareas de reunir dos criterios: Debe ser al menos un número de tareas como hilos (o núcleos) Preferible que haya más tareas que hilos Mayor flexibilidad en la planificación Ayudar a lograr una carga más equilibrada entre los hilos La cantidad de cómputo dentro de una tarea debe ser lo suficientemente grande como para compensar la sobrecarga de gestión de tareas e hilos
Si la descomposición inicial no reúne estos criterios, deben considerarse descomposiciones alternas
24 ACTIVIDAD: ejemplo de definición de tareas Considere una aplicación de procesamiento de imágenes, donde cada pixel es independiente
¿Cuál es el nivel apropiado de descomposición de tareas? Tarea == un pixel Tarea == una línea Tarea == bloques dentro de la imagen
25 Administrando Dependencias en Soluciones en el Patrón de Paralelismo de Tareas Ordenar los acuerdos entre las tareas pueden ser manejados para forzar grupos de tareas a ejecutarse en orden (Gp:) Paisaje
(Gp:) Construir Paredes
(Gp:) Poner techo
(Gp:) Tejas en el techo
(Gp:) Instalación Eléctrica
(Gp:) Enjarre
(Gp:) Parte Exterior
26 Gestionando Dependencias en Patrones de Solución de Paralelismo de Tareas Resolver dependencias de datos puede ser más complicado El caso más simple es tener no dependencias (vergonzosamente paralelas) Estrategias para manejar dependencias de datos entre tareas: Removerlas (replicando datos) Transformando variables de inducción Reducciones Protegiendo explícitamente (patrón de datos compartidos)
27 Calcula global X Calcula global Y Calcula global Z Envía señal X,Y,Z listos For i = 1, 10 Calcula a[i] = F(X,Y,Z,b[i]) Dependencias Removibles No una dependencia verdadera, pero una dependencia aparente que puede eliminarse con transformación de código La solución más simple sería crear, inicializar, y usar variables locales Puede implicar la replicación de trabajo dentro de los hilos (Gp:) Algoritmo Serial: (Gp:) Calcula X Calcula Y Calcula Z For i = 1, 20 Calcula a[i] = F(X,Y,Z,b[i])
Espera que X,Y,Z estén listos
For i = 11, 20 Calcula a[i] = F(X,Y,Z,b[i]) Hilo 1 Hilo 2 Calcula local X Calcula local Y Calcula local Z For i = 11, 20 Calcula a[i] = F(X,Y,Z,b[i]) Calcula local X Calcula local Y Calcula local Z For i = 1, 10 Calcula a[i] = F(X,Y,Z,b[i])
28 Dependencias Removibles Las variables de inducción se incrementan en cada pasada dentro del ciclo
Arreglar reemplazando los incrementos con expresiones equivalentes en función al índice del ciclo i1 = 4;i2 = 0;for (I = 0; I < N; I++) { B[i1++] = … ; i2 = i2 + I; A[i2] = … ;} for (I = 0; I < N; I++) { B[I+4] = …; A[((I+1)*I)/2)] = …;}
29 Dependencias “Separables” Dependencias en estructuras de datos compartidas usadas para acumular de datos calculados en cada hilo Mueve la acumulación fuera de la concurrencia: Replica los datos a cada hilo, inicialízalos como se requiera Ejecuta las tareas usando la copia local de la estructura de datos Al completarse, combina todas las copias en una estructura de datos global
30 Dependencias “Separables” El ejemplo más común: Reducción Una colección de datos se reduce a un solo valor aplicando una operación binaria a todos los elementos de la colección La operación binaria debe ser asociativa y conmutativa for (int i = 0; i < N; i++) sum += a[i] * b[i];
31 Protección Explícita de Datos Compartidos Si la dependencia no puede removerse o separarse desde las tareas, entonces los datos compartidos que se actualizan deben protegerse Implementa una región crítica en el código que accesa datos compartidos Si se hace cualquier actualización, todos los accesos (lectura y escritura) deben estar en una región crítica Agrega lógica de programación para forzar la exclusión mutua en una región crítica Usa objetos de sincronización apropiada para crear exclusión mutua
32 Planificando Tareas Las tareas deben asignarse a hilos para que se ejecutenPlanifica tareas con carga de trabajo balanceadaUsuales dos tipos de planificación Planificación estática Las tareas se asignan a hilos al inicio del cómputo y no cambian Fácil de programar y provoca poca sobrecarga Debe usarse siempre que sea posible Planificación dinámica Las tareas se asignan conforme procede el cómputo
33 Consideraciones de Planificación Estática El trabajo debe diferenciarse con id de hilo único para cada hilo Si las tareas son colecciones de llamadas a funciones independientes separadas Agrupa las llamadas en tareas que son asignadas a hilos
Si las tareas son iteraciones de ciclos, dos planificaciones posibles Divide el número total de iteraciones entre el número de hilos y asigna un bloque de iteraciones a los hilos Inicia cada conjunto de hilos de iteración por número de id de hilo (0..N-1), cada hilo calcula cada enésima iteración
34 Consideraciones de Planificación Dinámica Usada cuando el tamaño de la ejecución de tareas es variable e impredecible
Métodos posibles para planificación dinámica de tareas Usar una estructura compartida para mantener las tareas Si las tareas se pueden encapsular dentro de una estructura, crea una cola global que tener y despachar tareas cuando los hilos necesiten más trabajo Si las tareas se almacenan en un archivo, los hilos comparten acceso para leer tareas del archivo
35 Consideraciones de Planificación Dinámica Métodos posibles para planificación dinámica de tareas Algunas tareas pueden tomar pre-procesamiento en orden de estar listas para que se les asigne computación Usa un hilo extra para obtener tareas listas para los hilos y asignarlas a hilos cuando sean solicitadas (Patrón maestro/esclavo) Usar un hilo extra para poner tareas en una cola compartida para que otros hilos las tomen conforme las necesiten (patrón Productor/Consumidor)
Si las tareas están indexadas, crea un contador compartido para mantener registro de y asignar la próxima tarea a ejecución
36 Z X Y CASO DE ESTUDIO: Evitar Desastres Aereos
37 CASO DE ESTUDIO: Evitar Desastres Aereos Escenario de un conjunto de aviones alrededor de un aeropuerto
¿Hay dos aviones demasiado cerca entre ellos mismos? Si, envía un mensaje de advertencia y registra el evento Lleva registro del número de advertencias generadas por un avión en el escenario Será usado para determinar cual vuelo puede estar más en peligro
38 CASO DE ESTUDIO: Evitar Desastres Aereos Los aviones tienen un número de vuelo y una posición actual en un espacio 3-D X y Y son la posición con respecto a la tierra (mapa) Z es la altitud actual
Pseudo-código en la siguiente diapositiva El cálculo de la distancia se usa para determinar peligro potencial
39 CASO DE ESTUDIO: Posicionamiento de Aviones function AirplanePositions (N, M, Flights) int const N, M; //Número de aviones, aeropuertos Array of Airplane_t :: Flights(N); // arreglo de estructuras de aviones
Real :: distX, distY, distZ, distance
loop [j = 0, N] loop [k = j+1, N] distX = (Flights[j].Xcoord – Flights[k].Xcoord) ^ 2 distY = (Flights[j].Ycoord – Flights[k].Ycoord) ^ 2 distZ = (Flights[j].Zcoord – Flights[k].Zcoord) ^ 2 distance = sqrt(distX + distY + distZ) if (distance < SAFETY_MARGIN) PrintWarning(Flights[j],Flights[k]) Flights[j].numWarnings++ Flights[k].numWarnings++ end loop[k] end loop[j] end function AirplanePositions
40 function AirplanePositions (N, M, Flights) int const N, M; //number of planes, airports Array of Airplane_t :: Flights(N); // array of planes structs
Real :: distX, distY, distZ, distance
loop [j = 0, N] loop [k = j+1, N] distX = (Flights[j].Xcoord – Flights[k].Xcoord) ^ 2 distY = (Flights[j].Ycoord – Flights[k].Ycoord) ^ 2 distZ = (Flights[j].Zcoord – Flights[k].Zcoord) ^ 2 distance = sqrt(distX + distY + distZ) if (distance < SAFETY_MARGIN) PrintWarning(Flights[j],Flights[k]) Flights[j].numWarnings++ Flights[k].numWarnings++ end loop[k] end loop[j] end function AirplanePositions El cálculo de la distancia entre cada avión es una tarea CASO DE ESTUDIO: Posicionamiento de Aviones– Definir tareas
41 function AirplanePositions (N, M, Flights) int const N, M; //Número de aviones, aeropuertos Array of Airplane_t :: Flights(N); // arreglo de estructuras de aviones
Real :: distX, distY, distZ, distance
loop [j = 0, N] loop [k = j+1, N] distX = (Flights[j].Xcoord – Flights[k].Xcoord) ^ 2 distY = (Flights[j].Ycoord – Flights[k].Ycoord) ^ 2 distZ = (Flights[j].Zcoord – Flights[k].Zcoord) ^ 2 distance = sqrt(distX + distY + distZ) if (distance < SAFETY_MARGIN) PrintWarning(Flights[j],Flights[k]) Flights[j].numWarnings++ Flights[k].numWarnings++ end loop[k] end loop[j] end function AirplanePositions Dar a cada hilo una copia local de esas variables de trabajo La Actualización de variables compartidas debe protegerse Cada hilo necesitará una copia local de los índices del ciclo j,k CASO DE ESTUDIO: Posicionamiento de Aviones – Dependencias
42 CASO DE ESTUDIO: Posicionamiento de Aviones ¿Cómo deben planificarse las tareas? Planificación Estática Divide hasta N aviones y asígnalos a hilos Asignar N/(# de hilos) aviones a un hilo Asignar cada n-ésimo avión a cada hilo, iniciar con id del hilo Planificación Dinámica Establecer contador global (0..N-1) Los hilos acceden el contador para el siguiente[j], incrementa el contador Deben proteger el acceso e incrementar el contador global loop [j = 0, N] loop [k = j+1, N] if (NOT j.Landed OR NOT k.Landed) then distX = (Flights[j].Xcoord – Flights[k].Xcoord) ^ 2 distY = (Flights[j].Ycoord – Flights[k].Ycoord) ^ 2 distZ = (Flights[j].Zcoord – Flights[k].Zcoord) ^ 2 distance = sqrt(distX + distY + distZ) if (distance < SAFETY_MARGIN) LogWarning(Flights[j],Flights[k]) Flights[j].numWarnings++ Flights[k].numWarnings++ end loop[k] end loop[j]
43 ACTIVIDAD: Dinámica Molecular ¿Qué son las tareas dentro del pseudocódigo? ¿Hay dependencias? ¿Cómo pueden resolverse? ¿Cómo deben planificarse las tareas para ejecutarse en hilos?
44 ACTIVIDAD: Código de la Dinámica Molecular Colecciones de átomos calculan fuerzas entre pares de átomos Solo pares de átomos que están con un radio igual a un límite preestablecido La lista de vecinos para cada átomo determina que otros átomos están dentro del radio Tercera ley de Newton: La fuerza del Atom[i] en el Atom[j] es el negativo del Atom[j] en el Atom[i] Si el Atom[j] está en la lista de vecinos del Atom[i], entonces el Atom[i] no estará en la lista para el Atom[j] Pseudo-código en la siguiente diapositiva No se requieren cálculos físicos para este ejercicio No se muestran como los vecinos hacen sus actualizaciones
45 ACTIVIDAD: Código de la Dinámica Molecular function non_bonded_forces_all (N, Atoms, neighbors, Forces) Int const N //number of atoms Array of Real :: atoms(3,N) // 3D coordinates Array of Real :: Forces(3,N) // force in each dimension Array of List :: neighbors(N) // atoms in cutoff volume Real :: forceX, forceY, forceZ
loop [i] over atoms loop [j] over neighbors(i) forceX = non_bonded_force_pair(atoms(1,i), atoms(1,j)) forceY = non_bonded_force_pair(atoms(2,i), atoms(2,j)) forceZ = non_bonded_force_pair(atoms(3,i), atoms(3,j)) Forces(1,i) += forceX; Forces(1,j) -= forceX; Forces(2,i) += forceY; Forces(2,j) -= forceY; Forces(3,i) += forceZ; Forces(3,j) -= forceZ; end loop[j] end loop[i] end function non_bonded_forces_all
46 Agenda Patrón de estructura de lenguaje El patrón de paralelismo de tareas El patrón de descomposición geométrica Estructuras de Soporte Resumen
47 Estructuras de Algoritmos del Espacio de Diseño (Gp:) Pipeline
(Gp:) Organizado por flujo de datos
(Gp:) ¿Lineal?
(Gp:) ¿Recursivo?
(Gp:) Organizado por tareas
(Gp:) ¿Lineal?
(Gp:) ¿Recursivo?
(Gp:) Organizado por datos
(Gp:) Datos Recursivos
(Gp:) ¿Regular?
(Gp:) ¿Irregular?
(Gp:) Paralelismo de tareas
(Gp:) Descomposición Geométrica
(Gp:) Divide y Vencerás
(Gp:) Coordinación basada en eventos
¿Cómo está estructurado el cómputo?
48 Patrón de Descomposición Geométrica Problema: ¿Como un algoritmo paralelo puede estar organizado alrededor de una estructura de datos que puede descomponerse en “fragmentos” independientes y concurrentemente actualizables?
49 Patrón de Descomposición Geométrica Ejemplos: Predicción del clima – Divide el área de interés en secciones discretas, no sobrepuestas; calcula los efectos del viento, tierra, sol, humedad, clima en secciones vecinas, etc. Iterativamente
Fractales de Newton-Raphson – Para cada punto dentro de un plano complejo, calcula el número de iteraciones requeridas para alcanzar la raíz del polinomial; punto de color apropiadamente
50 Contexto del Patrón de Descomposición Geométrica Muchos problemas pueden entenderse mejor como una secuencia de operaciones en el núcleo de una estructura de datos Todos los elementos de la estructura se actualizan o se usan para cómputo
51 Contexto del Patrón de Descomposición Geométrica La estructura se divide en sub-estructuras contiguas o sub-regiones Arreglos: divide entre una o más dimensiones
Listas: define sublistas de elementos discretos
Grafos y Árboles: construye sub-grafos o sub-árboles
52 Contexto del Patrón de Descomposición Geométrica Usaremos el término genérico fragmento para referir una sub-región
La descomposición de datos en fragmentos implica una división del cómputo en tareas para operar en elementos de cada fragmento Las tareas se ejecutarán concurrentemente Cada tarea actualizará el fragmento asociado Las tareas pueden requerir datos de fragmentos vecinos que deben ser compartidos Los fragmentos vecinos contienen datos que estaban “cerca” en la estructura de datos original
53 Propuestas del Patrón de Descomposición Geométrica Metas: simplicidad, portabilidad, escalabilidad, y eficiencia Fragmentos de datos deben asignarse a hilos El balanceo de carga puede ser un factor, especialmente cuando se usan fragmentos de tamaño variable El cómputo asociado debe ser ejecutado por el hilo Asegurarse que los datos necesarios para actualizar los fragmentos están disponibles cuando se requieren Los datos desde dentro de un fragmento son de fácil acceso Acceder datos esenciales de fragmentos vecinos pueden requerir coordinación entre hilos
54 Patrones de Soluciones de Descomposición Geométrica Deben considerarse las siguientes actividades clave: Descomposición de datos Particionar la estructura de datos global en fragmentos Considera granularidad y la forma de los fragmentos Operación de intercambio Asegurarse que cada tarea tenga acceso a todos los datos necesarios para la actualización ¿Se requiere tener disponibles datos “externos”? Operación de actualización (cómputo) Actualizando los elementos dentro del fragmento Normalmente la mayor parte del cómputo Distribución de datos y planificación de tareas Como mapear fragmentos y asociar cómputo a hilos
55 1. Descomposición de Datos – Granularidad La granularidad de la descomposición de los datos tendrá un impacto significativo en el rendimiento y eficiencia de la aplicación Descomposición Grano-grueso Menos fragmentos pero más grandes Requiere menor cantidad de datos compartidos (sincronización/comunicación) Descomposición Grano-fino Más fragmentos pero más pequeños Puede haber (mucho) más fragmentos que hilos; más fácil para el balanceo de carga Mayor cantidad de datos compartidos y sincronización
56 1. Descomposición de Datos – Granularidad La granularidad óptima puede ser difícil de obtener matemáticamente al principio de la computación Experimentos para encontrar el mejor tamaño en la descomposición Si las cargas de trabajos varían entre ejecuciones, el tamaño de la descomposición puede ser parametrizable dentro de la aplicación Bueno para escalabilidad de la aplicación
57 1. Descomposición de Datos – Forma (Arreglo) La forma de los fragmentos puede afectar la cantidad de comunicación y sincronización requerida Los datos a compartir usualmente son valores de frontera de los fragmentos Datos compartidos escalan de la superficie de los fragmentos La computación escala con el volumen de los fragmentos (número de elementos de datos en un fragmento) (Gp:) 16 celdas, 4 compartidas
(Gp:) 16 celdas, 8 compartidas
58 1. Descomposición de Datos – Forma (Arreglo)
Tamaño y forma de los fragmentos pueden ser afectados por otros factores Tamaño línea caché, renglón-mayor o columna-mayor, código fuente antes/después (Gp:) 16 celdas, 4 compartidas
(Gp:) 16 celdas, 8 compartidas
59 1. Descomposición de Datos – Forma (Gráfico) La superficie del subgrafo puede dividirse a lo ancho para dividirse en subgrafos Asume que los datos deben compartirse a través de las aristas
La mejor división de nodos a hilos para minimizar vecinos asignados a hilos diferentes
60 ACTIVIDAD: Misión de descomposición
Describe esquemas de descomposición para los siguientes conjuntos de datos: Red de cuadros representando la masa de tierra y costa de Australia Catálogo de libros en una librería Gráfica que representa un mapa de 3000 ciudades en México (nodos) y carreteras entre ellos (aristas)
61 2. Operación de Intercambio Factor clave en un patrón correcto de Descomposición Geométrica Asegurar que el intercambio de datos entre segmentos vecinos sea eficiente ¿Copiar datos a estructuras de datos locales o accederlos conforme se necesiten?
62 2. Operación de Intercambio Copiar datos a una estructura de datos local Si hay datos disponibles antes de una operación de actualización y no cambiará durante la copia Requiere memoria extra por hilo, pero no bloqueos en las copias Acceder los datos conforme se requieren Obtiene ventaja de la memoria compartida entre hilos Retrasos en la coordinación entre hilos mientras los datos son necesitados (Gp:) Debe haber coordinación entre hilos para asegurarse que los datos están disponibles y no cambiarán durante el intercambio
63 3. Operación de Actualización Ejecución de las tareas asociadas actualizará concurrentemente la estructura de datos
64 3. Operación de Actualización Consideraciones de la codificación para la interacción de intercambio y actualización Si todos los datos están disponibles al inicio de las tareas y no cambiarán durante el cómputo, la paralelización será más fácil y probablemente eficiente Si se van a copiar datos no locales de otros fragmentos antes de operaciones de cómputo de actualización, añade una fase de recopilación de datos antes de comenzar la actualización Si no se van a acceder datos no locales a través de operaciones de actualización, agrega código para asegurarse que se encuentran los datos correctos y garantizar que se observa un protocolo de acceso adecuado (exclusión mutua) Mezclar operaciones de intercambio y actualización pueden complicar la lógica de la aplicación, especialmente para asegurar que se obtienen datos correctos
65 4. Distribución de Datos y Planificación de Tareas Determina que hilos actualizarán que segmentos de datos La distribución estática es lo más simple La coordinación para el intercambio será sencilla para determinar e implementar Lo más apropiado cuando la cantidad de cómputo en las tareas es uniforme La distribución dinámica es útil para el balanceo de carga Requiere (muchas) más tareas que hilos La operación de intercambio será más compleja Debe asegurarse que las actualizaciones de datos no-locales se ha completado
66 4. Distribución de Datos y Planificación de Tareas ¿Qué hay acerca de redistribución dinámica de la distribución estática inicial? Si la cantidad de trabajo por hilo cambia sobre el curso del cómputo Ejemplo: operación de matriz que elimina renglones/columnas Aplicación que puede reconfigurar la distribución de tareas/datos para la carga de trabajo La Ganancia en el rendimiento debe superar la sobrecarga añadida por la re-distribución
67 CASO DE ESTUDIO: Multiplicación de Matrices for (i = 0; i < M; i++) for (j = 0; j < N; j++) C[i][j] = 0.0;
for (i = 0; i < M; i++) for (j = 0; j < N; j++) for (k = 0; k < L; k++) C[i][j] += A[i][k] * B[k][j]; B A C ¿Qué se puede calcular de manera independiente? Elementos individuales de C Renglones de C (usando todo de B) Columnas de C (usando todo de A) Bloques de C
68 CASO DE ESTUDIO: Multiplicación de Matrices ¿Qué estructura de datos grande necesita ser actualizada?
¿Cómo debe descomponerse la estructura de datos? ¿Qué granularidad será la mejor?
¿Qué datos necesitan compartirse entre tareas asociadas con los fragmentos de datos? ¿Hay datos no locales que requieren intercambiarse?
¿Cómo debemos asignar los fragmentos a los hilos? ¿Estático o Dinámico?
69 CASO DE ESTUDIO: Multiplicación de Matrices con Posibles Respuestas ¿Qué estructura de datos grande necesita ser actualizada? La matriz C
¿Cómo debe descomponerse la estructura de datos? ¿Qué granularidad será la mejor? Elementos individuales parece que sería grano demasiado fino Grupos de renglones entran en renglones más accesados y es grano grueso Los bloques pueden usarse enfocándose en el tamaño y utilización del caché
70 CASO DE ESTUDIO: Multiplicación de Matrices con Posibles Respuestas ¿Qué datos necesitan compartirse entre tareas asociadas con los segmentos de datos? ¿Hay datos no locales que requieren intercambiarse? Elementos de los arreglos A y B son compartidos (pero no actualizados) Si estos caben en la memoria, pueden compartirse sin intercambiarse
¿Cómo debemos asignar los segmentos a los hilos? ¿Estático o Dinámico? Como no se requiere intercambio de datos, la distribución estática es la más simple
71 for (i = 0; i < M; i++) for (j = 0; j < N; j++) C[i][j] = 0.0;
for (i = 0; i < M; i++) for (j = 0; j < N; j++) for (k = 0; k < L; k++) C[i][j] += A[i][k] * B[k][j]; (Gp:) Modifica los límite del ciclo “i”, basado en un identificador de hilo único, asignando grupos de renglones a hilos individuales
(Gp:) Cada hilo requerirá copias locales de todas las variables índices de los ciclos
CASO DE ESTUDIO: Multiplicación de Matrices
72 ACTIVIDAD: Juego de la vida ¿Cuál es la mayor cantidad de datos que pueden actualizarse concurrentemente? ¿Cómo deben descomponerse estos datos? ¿Cómo deben planificarse los datos y tareas para ejecutarse en hilos? ¿Qué consideraciones se necesitan tomar en cuenta para la carga de trabajo?
73 Agenda Patrón de estructura de lenguaje El patrón de paralelismo de tareas El patrón de descomposición geométrica Estructuras de Soporte SPMD Paralelismo de Ciclos Maestro/Esclavo Resumen
74 Estructuras de Soporte, Espacio de Diseño Bloques de construcción de alto nivel usados para organizar el código fuente Categorizados en estructuras de programa y estructura de datos Cola compartida Paralelismo de ciclos Maestro esclavo Estructuras del Programa Estructuras de Datos Datos compartidos SPMD Arreglo distribuido Fork/join Fork/join
75 Patrón SPMD Problema ¿Cómo estructuramos un programa paralelo para hacer iteraciones entre hilos que sean fácilmente manejables para integrarlos con los núcleos de computación? Contexto Las iteraciones entre hilos deben estar bien orquestadas para lograr soluciones correctas y eficientes Muchos algoritmos paralelos tienen operaciones similares llevadas a cabo por cada hilo, pero puede haber algunos cuantos requerimientos ligeramente diferentes para un conjunto de hilos o datos Solo los algoritmos más complejos necesitan instrucciones y flujos de datos muy diferentes en cada hilo
76 Patrón SPMD Propuesta Sería más fácil balancear las necesidades conflictivas de escalabilidad y de mantenimiento dentro de una solo código fuente en vez de que sea a través de varios archivos fuentes
77 Patrón SPMD – Solución Una sola aplicación creará hilos para ejecutar código y funciones dentro del código fuente Dada la naturaleza de la programación multihilos, el patrón SPMD es el default
78 Patrón SPMD – Solución Codificando Elementos para implementar el patrón SPMD Obtener un identificador único Asignar un ID para cada hilos, usualmente de 0..N-1 Usa el ID para diferenciar comportamiento entre hilos diferentes Las instrucciones de saltos pueden usarse para asignar bloques de código Usar el ID en los cálculos del índice del ciclo para dividir iteraciones entre los hilos
79 Patrón SPMD – Solución Distribuye datos Decompone datos globales en fragmentos y accede los fragmentos basándote en el ID Finaliza Si datos globalmente relevantes fueron distribuidos entre hilos, se requieren recombinar los resultados parciales
80 Patrón SPMD – Discusión Los programas SPMD están mas cercanamente alineados con ambientes distribuidos de paso de mensajes
Un solo programa que crea hilos es el default para la programación multihilos Los hilos dentro del mismo proceso comparten código y datos Más relevante con modelos de hilos generales que OpenMP
81 Patrón de Paralelismo de Ciclos Problema ¿Como estructurar un programa paralelo de un programa serial donde un conjunto de ciclos computacionalmente intensivos dominan el tiempo de ejecución?
82 Patrón de Paralelismo de Ciclos Contexto Un gran número de aplicaciones científicas y técnicas hacen uso de construcciones iterativas (basadas en ciclos) La meta es “hacer evolucionar” código secuencial en código paralelo transformando ciclos para ejecutar iteraciones separadas en hilos Las iteraciones de ciclos deben funcionar bien como tareas paralelas Computacionalmente intensivas Expresar suficiente concurrencia La mayoría independientes Quitar las dependencias entre ciclos si están presentes
Este patrón es particularmente relevante para usar OpenMP, Intel TBB
83 Patrón de Paralelismo de Ciclos Equivalencia Secuencial Programa que arroja resultados idénticos con uno o muchos hilos Errores de variaciones de redondeo pueden ser aceptables Código secuencialmente equivalente es más fácil de escribir y mantener Paralelismo Incremental Es más fácil mantener la correctud si las transformaciones del ciclo pueden hacerse y probarse una a la vez Puede ser difícil con modelos generales de hilos y distribución de datos a segmentos locales (se necesita transformación de “todo el código”)
84 Patrón de Paralelismo de Ciclos Utilización de Memoria Patrones de acceso de datos deben caber bien con las jerarquías de memoria Dividir las iteraciones para los hilos puede arruinar los patrones de acceso secuencial Puede ser necesario re-estructurar los para un mejor acceso
85 Patrón de Paralelismo de Ciclos – Solución Un estilo de programación alineado con OpenMP, Intel TBB Modelos generales de paralelismo pueden usarse con asignaciones de iteraciones de ciclos provistas por el programador
86 Patrón de Paralelismo de Ciclos – Solución Codificando elementos para implementar el patrón de paralelismo de ciclos Emcontrar hotspots Identifica los ciclos computacionalmente más intensivos inspeccionando el código, entendiendo el algoritmo, o usa un programa para el análisis Eliminar dependencias de los ciclos Encuentra dependencias entre iteraciones o conflictos de datos Remueve dependencias o protege daos con sincronización Paraleliza los ciclos Divide las iteraciones entre hilos Optimiza la planificación de ciclos Planifica iteraciones de ciclos para asegurar el balanceo de carga
87 Patrón de Paralelismo de Ciclos – Consideraciones El tiempo de cómputo dentro de las iteraciones debe ser suficiente para superar la sobrecarga de crear hilos y asignarles trabajo Solución: Mezclar hilos Dada una secuencia de ciclos con rangos de índices consistentes, mezclar esos ciclos en un solo ciclo incrementará el trabajo por iteración del ciclo resultante
88 Patrón de Paralelismo de Ciclos – Consideraciones El número más grande de iteraciones disponibles, habrá mayor flexibilidad para decisiones de planificación Solución: Unir ciclos anidados Combinar ciclos anidados puede llevarnos a un solo ciclo con un contador grande de iteraciones Contadores de iteraciones grandes pueden también permitir mejores oportunidades de superar la sobrecarga
89 Ejemplo de unir hilos #define N 23 #define M 1000
. . .
for (k = 0; k < N; k++) for (j = 0; j < M; j++) w_new[k][j] = DoSomeWork(w[k][j], k, j); #define N 23 #define M 1000
. . .
for (kj = 0; kj < N*M; kj++) { k = kj / M; j = kj % M; w_new[k][j] = DoSomeWork(w[k][j], k, j); } (Gp:) Un número primo de iteraciones nunca permitirá un balanceo de carga perfecto
(Gp:) ¿Paraleliza el ciclo interno? ¿Hay suficientes iteraciones para superar la sobrecarga de la gestión de los hilos?
(Gp:) DIV y MOD con el valor límite del ciclo interno Estos cálculos son sobrecarga
(Gp:) Un número grande de iteraciones da más oportunidad de balancear la carga y eliminar la sobrecarga
90 Dividendo Iteraciones de un Ciclo – OpenMP Añade pragma de OpenMP para dividir las iteraciones entre hilos Añade cláusulas de ambiente de datos y planificación como sea necesario #define N 23 #define M 1000
. . .
#pragma omp for private(k,j) schedule(static, 500) for (kj = 0; kj < N*M; kj++) { k = kj / M; j = kj % M; w_new[k][j] = DoSomeWork(w[k][j], k, j); }
91 Calculo punto inicial (start) y final (end) para las iteraciones de los ciclos basada en el número de hilos y número identificador del hilo #define N 23 #define M 1000 #define numThreads 4
. . .
int start = ((N*M)/numThreads) * myID; int end = ((N*M)/numThreads) * (myID+1); . . . if (myID == (numThreads-1)) end = N*M;
. . .
for (kj = start; kj < end; kj++) { k = kj / M; j = kj % M; w_new[k][j] = DoSomeWork(w[k][j], k, j); } (Gp:) Estas deben ser privadas para cada hilo
(Gp:) Asegúrate que todas las iteraciones se incluyen
Dividendo Iteraciones un Ciclo – Divide en Segmentos
92 #define N 23 #define M 5323 #define numThreads 16
. . .
int start = ((N*M)/numThreads) * myID; int end = ((N*M)/numThreads) * (myID+1); . . . if (myID == (numThreads-1)) end = N*M;
. . .
for (kj = start; kj < end; kj++) { . . . } 23 * 5323 = 122,429 iteraciones (Gp:) 13 iteracionesextras!
122,429 / 16 = 7651.8125 #define N 23 #define M 5323 #define numThreads 16
. . .
int start = (int)((float)(N*M)/numThreads) * myID; int end = (int)((float)(N*M)/numThreads) * (myID+1); . . . if (myID == (numThreads-1)) end = N*M;
. . .
for (kj = start; kj < end; kj++) { . . . } (float) (float) Dividendo Iteraciones del Ciclo – Balanceo de carga
93 Rango de valores de myID es [0..numThreads-1] Buen balanceo de cargaen el número de iteraciones Entre ±1 entre cualquiera de los hilos Fácilmente codificado, no se pueden perder iteraciones Ten cuidado de problemas potenciales de acceso a memoria y caché #define N 23 #define M 1000 #define numThreads 4
. . .
for (kj = myID; kj < N*M; kj+=numThreads) { k = kj / M; j = kj % M; w_new[k][j] = DoSomeWork(w[k][j], k, j); } (Gp:) Cada hilo hace cada iteración (numThreads)th
Dividendo Iteraciones del Ciclo – Turno Rotatorio
94 ACTIVIDAD: Paralelismo de Ciclos ¿Qué tipo de asignación se utilizaría en los siguientes cálculos para dividir las iteraciones entre los hilos?
Computar el siguiente cuadro de una película animada por computadora Ciclo sobre renglones Ciclo sobre pixeles en un renglón (columnas) Calcula pixel
95 ACTIVIDAD: Paralelismo de Ciclos Buscar a través del catálogo de una librería para encontrar cuántos libros tienen la palabra “loop” en el título Un ciclo sobre las letras del alfabeto Un ciclo sobre los autores con la primera letra en el nombre Un ciclo sobre los libros por autor Incrementar el contador global si el titulo tiene “loop
96 El Patrón Maestro/Esclavo Problema ¿Como debe un programa estar organizado cuando el diseño es dominado por la necesidad de un balancear dinámicamente el trabajo en un conjunto de tareas? Contexto Balancear la cargas de las tarea también domina la porción serial y causa sobrecarga Las cargas de trabajo de las tareas es variable e impredecible Porciones de código computacionalmente intensivas no mapean a ciclos simples Capacidad de núcleos en el sistema varían, cambian, impredecible Particularmente relevante para el patrón de Paralelismo de Tareas
97 El Patrón Maestro/Esclavo Forces Trabajo impredecible por tarea requiere una lógica de asignación dinámica Operaciones de balanceo de carga crean sobrecarga en la sincronización Menos tareas y más largas pueden reducir esto, pero restringen opciones Mantener el equilibrio entre balanceo de carga y mantener el código
98 El Patrón Maestro/Esclavo – Solución Hilo Maestro Inicia el cómputo Controla la distribución de tareas a ser asignada a los hilos esclavos Hilos Esclavos Están en un ciclo mientras haya más tareas por hacerse Aceptan tareas del hilo maestro Ejecutan cada tarea asignada Consideraciones en la Programación Distribución de tareas Detectar terminación y disposición de los esclavos
99 El Patrón Maestro/Esclavo Detectando Terminación Rendezvous Enviar una señal de terminación a cada esclavo Hasta que se recibe una tarea, los esclavos checan si hay nuevo trabajo o la terminación de la tarea
100 El Patrón Maestro/Esclavo Detectando Terminación Bolsa de tareas Si todas las tareas están inicialmente cargadas en una bolsa, una bolsa vacía significa que el cómputo se completó Añadir la terminación de tareas en la cola de tareas, después de todo el cálculo Por simplicidad, añade una tarea de terminación por hilo esclavo
Shared Monotonic Counter Counter greater than number of known tasks signals completion
101 CASO DE ESTUDIO: Implementación Rendezvous en el Código Maestro LockSyncObject(BWlock);// sincroniza acceso al contador num_waiting num_waiting++; if (num_waiting !=2) { // si no hay esclavo esperando… UnlockSyncObject(BWLock); SleepUntilWorkerArrives(); // …espera } else { WakeUpSleepingWorkerThread(); // despierta al esclavo num_waiting = 0; // resetea para el siguiente rendezvous UnlockSyncObject(BWLock); }
< TRANSFIERE DATOS, ASIGNA UNA TAREA NUEVA O ENVÍA TERMINACIÓN>
102 CASO DE ESTUDIO: Implementación Rendezvous, Código del Hilo Esclavo LockSyncObject(WorkerLock);//asegura la exclusion de otros esclavos LockSyncObject(BWlock);//sincroniza acceso al contador num_waiting num_waiting++; if (num_waiting !=2) { // si el maestro no está esperando… UnlockSyncObject(BWLock); SleepUntilBossArrives(); // …espera } else { WakeUpSleepingBossThread(); // despierta al maestro num_waiting = 0; // resetea para el siguiente rendezvous UnlockSyncObject(BWLock); } < TRANSFIERE DATOS, ASIGNA UNA TAREA NUEVA O ENVÍA TERMINACIÓN> UnlockSyncObject(WorkerLock);//permite el siguiente esclavo a rendezvous
103 ACTIVITY: Boss/Worker What type of task distribution method would be used on the following computations to divide iterations among threads?
Compute Mandlebrot set Loop over rows Loop over pixels in a row (columns) Compute pixel
104 ACTIVIDAD: Maestro/Esclavo Search through library catalog to find how many books have “loop” in the title Loop over letters of alphabet Loop over authors with first letter in name Loop over books by author Increment global counter if title has “loop”
105 Agenda Patrón de estructura de lenguaje El patrón de paralelismo de tareas El patrón de descomposición geométrica Estructuras de Soporte Resumen
| Página siguiente |