Ejercicios · Infra · Estrategias de paralelizacion¶
Estrategias de paralelización: descomposición, granularidad y balanceo. Los apartados van en el orden de la clase y todos se resuelven en el navegador, sin instalar nada. Cada uno reproduce el código que se midió en la sesión: lo que cambia es que aquí el reparto se ve tarea por tarea, y antes de ver un número toca escribirlo.
La pregunta antes del código¶
Qué cambió entre las dos filas¶
La misma tabla con que abrió la clase: el mismo programa, los mismos cuatro hilos, y en una fila repartir deja la ejecución dieciséis veces más lenta mientras en la otra la deja casi cuatro veces más rápida. Tres preguntas sobre esa tabla, cada una con cuatro respuestas, y cada respuesta equivocada dice por qué no.
La tercera es la que más se ve en la práctica: un ciclo envuelto en hilos que tarda lo mismo, y la conclusión apresurada que suele salir de ahí.
Descomposición de datos¶
Cortar el vector en trozos¶
El reparto exacto de con_hilos: paso = n / k, cada hilo recibe
[i·paso, (i+1)·paso) y el último se lleva además el residuo. Antes de ver la
barra, escoja cuántos elementos recibe el último hilo con diez elementos y
cuatro hilos. El reparto que parecía parejo no lo es, y el hilo que más recibe
es el que marca cuándo termina todo.
Al final está la tabla de los 200 millones de enteros (98, 51, 38 y 38 ms) y una pregunta: por qué ocho hilos no mejoran a cuatro. Las tres respuestas equivocadas son las que más se oyen.
Descomposición de tareas¶
Tres recorridos, tres hilos¶
El máximo, la suma y los pares de un vector de 50 millones, cada uno en su hilo. Antes de ver la medida, decida cuánto acelera: la respuesta no es tres, y las dos razones por las que no llega están en la retroalimentación. Después, qué hace un cuarto hilo cuando solo hay tres trabajos, y cuándo esta forma de repartir le gana a partir los datos.
El árbol del mergesort¶
La recursión de ordenar_par sobre 20 millones de enteros, dibujada por
niveles. Antes de mover la profundidad de corte, prediga cuántos hilos se crean
con profundidad tres: se lanza un hilo por división y no dos, porque la mitad
derecha la resuelve el hilo que ya venía. El botón Siguiente recorre los
pasos en el orden en que el código los ejecuta: dividir, lanzar, resolver,
join, mezclar. En cada mezcla se ve cuántas corren al tiempo, y la de arriba
siempre corre sola.
Queda una pregunta sobre la tabla medida con cuatro núcleos: por qué ocho hilos todavía ganan sobre cuatro, si núcleos hay los mismos.
Granularidad¶
El costo fijo de repartir¶
Las 400 tareas en tandas de cuatro hilos, con la columna de la relación tapada. Escoja en qué fila cruza el uno y después destápela: al lado aparece lo que da un modelo de dos perillas, el costo de crear y unir un hilo y el costo de cada iteración. Con 16 µs por hilo el modelo reproduce la tabla; suba el costo a 160 µs y el cruce se corre una fila. El cruce no es del algoritmo; es de la máquina donde se midió, y en otra se mide otra vez.
Balanceo de carga¶
Sesenta y cuatro tareas que no cuestan lo mismo¶
Las 64 tareas de balanceo.cpp, donde la tarea i cuesta i², y los cuatro
hilos. Antes de correr nada, escoja qué porcentaje del trabajo carga el hilo
que termina último con bloques contiguos. Después el reparto se ve tarea por
tarea en un Gantt por hilo, en tres versiones: bloques contiguos, por turnos y
por demanda con fetch_add. Las tareas que hizo cada hilo y el tiempo que
esperó se cuentan aparte.
La segunda predicción es cuántas veces más tarda el reparto contiguo que el reparto por demanda; en la máquina de la sesión dio 824 contra 379 ms. Por turnos casi lo arregla, hasta que la casilla de costos erráticos baraja los costos.
Delegar el reparto¶
Lo que parte blocked_range¶
tbb::blocked_range<int>(0, n, grano) se parte en dos mientras el tamaño
supere el grano. Prediga en cuántos subrangos queda un rango de mil con grano
cien y después mire el árbol. Con grano uno salen mil hojas, y ahí está la
razón de que el particionador automático deje de partir por su cuenta.
En la segunda parte, un programa imprime 2×10⁸ en paralelo y 10⁷ en secuencia. Cuál de los dos está bien, y qué se hace antes de mirar el reloj.
Dependencias¶
La suma de prefijos en dos pasadas¶
Doce valores en tres bloques y las dos pasadas de scan.cpp. La primera
pasada reporta el total de cada bloque; los tres desplazamientos los escoge
usted, y la segunda pasada arranca de lo que haya escogido. Si un
desplazamiento quedó mal, la fila sale con números plausibles y la
comparación elemento a elemento contra la versión secuencial marca en rojo
dónde se rompió. El selector de máximo es el ejercicio del saldo máximo
acumulado.
La medida de los 20 millones, 2.731 contra 1.636 ms, va al final, con una pregunta: qué pasa si la operación por elemento fuera una suma pelada.
Pipeline¶
Tres etapas y una cola entre cada par¶
Leer 10 ms, calcular 20, escribir 10, y 24 lotes. Escoja en cuántos milisegundos terminan antes de verlo; la tabla de quién trabaja en cada intervalo es la de la clase, con los huecos de la etapa de escribir. Dos encargos en la misma pantalla: bajar leer a 5 ms y ver que el total casi no se mueve, y poner dos réplicas en calcular y ver que baja a 270. La pregunta final es cuál etapa manda después de replicar.
Cómo elegir¶
Ocho situaciones¶
Ocho problemas de tres líneas y las mismas siete opciones para todos: las seis
estrategias de la tabla de la clase y dejarlo secuencial. Cada respuesta
equivocada dice por qué no y nombra el tema donde está la razón. Dos son
trampas: un ciclo con s[i-1] donde lo único que se hace es sumar, y una
ventana que parece una cadena de dependencias pero solo lee la entrada. El
marcador cuenta los aciertos a la primera.
Ejercicios de la sesión¶
Los seis ejercicios que se entregan están en las diapositivas, en el Campus
Virtual: la descomposición para el archivo de ventas, las 10.000 imágenes, el
saldo máximo, las mediciones sobre la carpeta codigo, el producto de Hadamard
en dos versiones y el algoritmo que se parte en dos.