← Volver a los ejercicios

Tiempo con P núcleos: las dos cotas y la estimación

Repartir un cálculo entre P núcleos choca con dos límites a la vez. Uno es el camino crítico, la cadena de operaciones que dependen una de otra y se ejecutan en fila por mucho hardware que haya: el tiempo no baja de D(e). El otro es el trabajo total, que hay que hacer completo y se reparte entre P núcleos a lo sumo: el tiempo no baja de W(e)/P. De ahí sale la estimación usual, D(e) + W(e)/P. La página corre la suma en árbol de un arreglo y cuenta las dos cifras sobre el recorrido, y después las usa con el número de núcleos del preset.

1. De dónde salen W(e) y D(e)

Cada hoja lee un elemento y cada nodo interno suma los dos resultados de abajo. El contador de la línea 5 cuenta las sumas, que son el trabajo, y el nivel del chip marca la profundidad del árbol de llamadas.

paso 0 de 0
sumas: 0 hojas: 0 nivel más profundo: 0

La suma de la línea 5 ocurre después de las dos llamadas recursivas, porque necesita sus dos resultados. Esa espera es lo que hace que el camino de la raíz a una hoja cuente como una cadena y no como trabajo repartible.

2. Las dos cotas y la estimación

TP ≥ D(e)    TP ≥ W(e)/P    TP ≈ D(e) + W(e)/P

¿Cuál de las dos cotas manda con el preset escogido?
¿Cuánto vale la estimación D(e) + W(e)/P con ese preset?

3. Lo que gana cada núcleo nuevo

D(e)W(e)/P

4. El piso que no se cruza

Con el n del preset y todos los núcleos que se quieran agregar, ¿de qué cifra no baja la estimación?

5. segmentRec con diez millones y cuatro núcleos

Para sumar un arreglo de diez millones de elementos, segmentRec reparte un trabajo del orden de n y su camino crítico es del orden de log2 n. Las dos primeras filas de la tabla salen de esas dos formas, que coinciden con lo que cuenta el recorrido de arriba en los tamaños pequeños; las últimas tres son las medidas de la sesión en una máquina de cuatro núcleos.

6. Para resolver por su cuenta

Tome la suma en árbol de un arreglo de 220 elementos. Encuentre el menor número de núcleos con el que el término del trabajo queda por debajo del término de la profundidad, y después el que haría falta para conseguir lo mismo con 230 elementos.