← Volver a los ejercicios

Divide y vencerás con umbral: cuántas tareas salen de ahí

Partir el arreglo en dos aprovecha dos núcleos. Para aprovechar cuatro u ocho hay que partir recursivamente, y partir hasta segmentos de un elemento sale más caro que sumarlos: cada partición lanza una tarea y coordinar tareas cuesta. El umbral es el punto donde la recursión deja de repartir y se pone a sumar. La condición que lo compara es estricta, y de ahí sale el segmento que se parte aunque mida exactamente el umbral.

1. Cuántas sumas secuenciales

Con un arreglo de 40000 elementos y UMBRAL = 10000, la recursión parte hasta que el segmento sea menor que el umbral.

¿Cuántas llamadas a sumSegment hace en total?

2. El recorrido, un paso a la vez

paso 0 de 0
sumas secuenciales: 0 llamadas a parallel: 0

Los contadores a la derecha de cada línea dicen cuántas veces se evaluó. El de la línea 2 cuenta las sumas secuenciales y el de la línea 4, las llamadas a parallel. El recorrido visita primero la mitad izquierda completa y después la derecha, que es el orden en que la recursión arma el árbol.

3. Qué decide el umbral

4. Para resolver por su cuenta

Escriba sumaPar(a: Array[Int], s: Int, t: Int, umbral: Int): Long, que sume el segmento con el mismo patrón de segmentRec. Mida el tiempo con diez millones de elementos para umbrales de 100, de 10000 y de un millón, y reporte cuál resultó mejor en su máquina.