Granularidad Es determinada por el número de tareas (=CPUs trabajando) y el tamaño del problema asignado a cada tarea. Fine-grained (grano fino): muchas tareas, pequeños problemas Coarse-grained (grano grueso): pocas tareas más grandes.
Grado de concurrencia Es el máximo número de tareas que corren en paralelo en un algoritmo. Puede ser menor que número de CPUs asignadas, por dependencia de las tareas. Grado promedio de concurrencia: número promedio de tareas en paralelo en un momento dado. Generalmente, grano fino ? más concurrencia
Conc.promedio= (4*10+2*6+1*11)/27=2.33 Conc.Promedio=(4*10+6+11+7)/34=1.88
Ruta crítica y grafo de interacción de tareas Ruta crítica: es la más larga ruta entre nodos iniciales y finales del grafo. En el ejemplo anterior (a) 10+9+8=27 (b) 10+6+11+7=34 En el grafo, los nodos representan tareas y las aristas conectan tareas que interactúan unas con otras. Pesos de los nodos: tiempo de cómputo. Pesos de aristas: costo de interacción (ej.: comunicación).
Ejemplo: multiplicación vector x matriz dispersa (sparse) Computar:
Solo para los A[i,j] ? 0. Suponer que hay n CPUs y se reparten las filas de A y los valores de b (ej.: CPU0 es dueña de b[0])
Mapeo Es el mecanismo por el que las tareas se asignan a los procesos Un proceso: proceso como se entiende en sistemas operativos, o parte de un proceso (hilo) Generalmente 1 proceso ??1 CPU/ core
Ejemplo
Técnicas de descomposición Más conocidas: Descomposición Recursiva Descomposición de datos Descomposición Exploratoria Descomposición Especulativa Las 2 primeras son más generales.
D. Recursiva Divide y vencerás, en forma recursiva Ej. quicksort
Ej: hallar mínimo número de un array A de n elementos Serial o secuencial: 1. procedure SERIAL_MIN (A, n) 2. begin 3. min = A[0]; 4. for i := 1 to n – 1 do 5. if (A[i] < min) min := A[i]; 6. endfor; 7. return min; 8. end SERIAL_MIN
Reformado : divide y vencerasEj: A={4,9,1,7,8,11,2,12}
Cambiado a recursivo 1. procedure RECURSIVE_MIN (A, n) 2. begin 3. if (n = 1) then 4. min := A[0]; 5. else 6. lmin := RECURSIVE_MIN (A, n/2); 7. rmin := RECURSIVE_MIN (&(A[n/2]), n – n/2); 8. if (lmin < rmin) then 9. min := lmin; 10. else 11. min := rmin; 12. endelse; 13. endelse; 14. return min; 15. end RECURSIVE_MIN
A un CPU A otro CPU
D. De datos Primero se particiona la data Luego se usa esa partición de la data para inducir la partición de las computaciones en tareas. Lo ideal sería que ambas particiones sean parejas en tamaño (cada proceso / CPU / core con data parecidas en tamaño y tareas parecidas en tiempo de cómputo)
Ej: multiplicación de matrices Parta cada factor en 4 submatrices. El resultado también. Cada submatriz del resultado se puede calcular por separado. Y que pasa si tengo 8 CPUs?
Ej: calcular frecuencias de itemsets en una tabla
Particionando data intermedia
D. exploratoria Se usan en problemas de búsqueda (ej.: en árboles) Se parte el espacio de búsquedas en subespacios más pequeños. Ej: puzzle de 15 cuadrados
D. especulativa Cuando en un algoritmo hay ramas que dependen de un IF (si es verdadero se hace una operación, si es falso se hace otra), se puede paralelizar ambas tareas ANTES de poder evaluar el IF, ejecutando ambas operaciones y esperar al IF para eliminar una y mantener la otra.
Ejemplo x=valoresPropios(matriz A) IF max(x)< 1 B=C+D ELSE B=X-Y
Tareas Características de las tareas: Generación: estática o dinámica Tamaño: uniforme o no uniforme Conocimiento del tamaño: se puede conocer de antemano o no? Tamaño de la data asociada a las tareas
Interacciones entre tareas Características: Estáticas vs Dinámicas Regular vs Irregular Read-only vs. Read-Write 1-way vs 2-way. Todas las read only son 1-way, pero las read-write pueden ser de cualquier tipo.
Ej. Regular: gradiente de una imagen para ver “bordes”
Mapeo para balance de carga Dos objetivos Reducir tiempo de interacción entre procesos Reducir el tiempo ocioso de los procesos Mutuamente excluyentes Mapeo estático vs dinámico
Esquemas de mapeo estático Mapeos basados en la partición de data para arrays: Bloques 1-D, 2-D, 3-D Ciclicos Aleatorios en bloque Basados en grafos:
Bloques
Cíclicos
Grafo de un lago, mapeo en 8 procesos
Mapeos basados en dependencia de tareas
Mapeo dinámico Centralizado: un master reparte las tareas a los procesos según su criterio. Tareas de una en una, o en chunks (“pedazos”) Distribuido: un proceso puede enviar o recibir las tareas de otro. Si P3 tiene mucha carga, delega algunas tareas a P7 que esta libre.
Localidad Grado en el que la data que reside en memoria de un CPU basta para el trabajo de esa CPU. Mientras más tenga que usar data “ajena”, menos localidad hay. En otros ramos de Computer Science tiene otros significados
Paralelismo y Localidad en Simulación Problemas físicos tienen paralelismo y localidad: Muchos objetos operan independientemente unos de otros. Los objetos generalmente dependen más de otros objetos cercanos que de los lejanos. Dependencia en objetos lejanos se puede simplificar. Algunos modelos científicos pueden crear paralelismo: Cuando un problema continuo se discretiza, la dependencia en el tiempo se limita a time steps cercanos. Efectos lejanos se pueden ignorar o aproximar. Puede haber paralelismo en varios niveles Ej.: varios circuitos se pueden simular a diferentes niveles, desde el de todo un aparato, hasta los componentes básicos individuales.
Algunas clases básicas de simulación Sistemas de eventos discretos: Ejs: “Game of Life,” circuitos lógicos. Sistemas de partículas: Ejs: bolas de billar, dispositivos semiconductores, galaxias. Variables agregadas que dependen de param. continuos: EDOs, ej: simulación de circuitos (Spice), estructuras mecánicas, cinética química. Variables continuas que dependen de param. continuos: EDPs, ej: calor, elasticidad, electrostática.
Muchas simulaciones combinan varias técnicas.
Resumen Eventos discretos Tiempo y espacio discretos Partículas Caso especial de sistema agregado Ec. Diferenciales ordinarias (EDOs) Sistemas agregados Entidades o posiciones discretas, tiempo continuo Ec. Diferenciales parciales (EDPs) Tiempo y espacio es continuo
Identificar problemas comunes y sus soluciones discreto continuo
Maximizando localidad de data Minimizar el volumen de intercambio de data. Ej.: gradiente, partir en 4 procesos como cuatro cuadrados pequeños vs 4 tiras largas Minimizar la frecuencia de interacciones. Ej.: multiplicacion vector matriz dispersa, con núm.CPUs < < núm. de filas
Minimizar congestión y hot spots Si 2 o más procesos quieren usar la misma data a la vez, donde por lo menos 1 de ellos quiere escribir: contención. Mientras ese lea+escriba, los otros no deberían correr. Cambiar el patrón de acceso (orden de las operaciones)
Que coincidan computaciones e interacciones Ej: mientras P0, P1 computan, P2 lee y/o escribe la variable x. Luego le tocara a P0. Otro ej.: usar comunicación asíncrona
Modelos de algoritmos paralelos Modelo data-parallel: ej.sumatoria Modelo gráfico de tareas: ej. Multp. Vector matriz dispersa Modelo de pool de tareas: mapeo dinámico de un loop es muchos sub-loops Modelo master-slave. Ej: montecarlo maestro esclavo Modelo pipeline o productor-consumidor Híbridos
| Página siguiente |