Escalabilidad de los ordenamientos

💡 En simple

“Escalable” quiere decir: si te doy más procesadores, ¿cuánto más grande tiene que ser el problema para que cada procesador siga igual de ocupado (misma eficiencia)?

Si basta con duplicar los datos, es muy escalable. Si hay que elevarlos al cuadrado o algo peor, apenas escala. La comparación entre la malla y el hipercubo de la PD5 es justo eso: cuál de las dos topologías pide menos datos para mantener la eficiencia.

El método (repaso del parcial)

Viene de Escalabilidad e isoeficiencia:

1. Trabajo W = T_s: el mejor secuencial. Para ordenar, W = n log n.
2. Overhead T_o = p·T_p − W: todo lo que los p procesadores gastan de más.
3. Eficiencia E = W / (W + T_o) = 1 / (1 + T_o/W).
4. E constante ⇔ W = K·T_o, con K = E/(1 − E). Despejar n en función de p: esa es la función de isoeficiencia.
5. Menor crecimiento = más escalable. Una isoeficiencia polinomial (p, p log p) es buena. Una exponencial (2^√p) es mala.

Cómo leerlo: la receta en cinco pasos, con los números del bitónico en malla. Se parte del T_p que da el enunciado, se multiplica por p, se resta el trabajo secuencial W para quedarse con el overhead T_o, se iguala W = K·T_o y se despeja n en función de p. Lo único que cambia de un ejercicio a otro es el T_p de la caja 1.

PD05, ejercicio 3a: bitónico en malla vs hipercubo (1 pt)

Enunciado: cómputo O((n/p) log n). Comunicación O(n/√p) en malla y O((n/p) log² p) en hipercubo. Analizar la escalabilidad y decidir qué modelo es más escalable.

Resolución paso a paso

Malla. T_p = (n/p)·log n + n/√p.

• p·T_p = n log n + n·√p
• T_o = p·T_p − n log n = n·√p
• E constante: n log n = K·n·√p ⇒ log n = K·√p ⇒ n ∝ 2^K√p

Hipercubo. T_p = (n/p)·log n + (n/p)·log² p.

• p·T_p = n log n + n·log² p
• T_o = n·log² p
• E constante: n log n = K·n·log² p ⇒ log n = K·log² p ⇒ n ∝ 2^{K log² p} (= p^{K log p})

Comparación. Las dos son exponenciales en el exponente que hay que comparar: √p frente a log² p.

p	√p (malla)	log² p (hipercubo)	¿cuál pide menos datos?
16	4	16	malla
1 024	32	100	malla
65 536 = 2¹⁶	256	256	iguales
2²⁰ ≈ 10⁶	1 024	400	hipercubo

Respuesta oficial de la PD: “Para la malla n ∝ 2^√p, para el hipercubo n ∝ 2^{log² p}. La malla escala mejor porque necesita menos trabajo (W) para mantener E constante.” Es correcta para p < 2¹⁶ = 65 536, que es cualquier cluster que uses en el curso.

Matiz: para p > 2¹⁶, √p crece más rápido que log² p y el hipercubo pasa a ser el más escalable. Es la conclusión asintótica de los libros: Grama et al., cap. 9 (conocimiento general). En el examen conviene dar la respuesta oficial y mencionar el cruce: demuestra que entiendes de dónde sale.

¿Cuántos datos hacen falta para mantener la eficiencia?

La función de isoeficiencia dice cuánto debe crecer el problema n cuando crece p para que E no baje. El eje vertical es log₂ n (constante K = 1): cada unidad más es el doble de datos. Menos es mejor (más escalable).

p = 2^10 = 1024

bitónico en malla: n ∝ 2^√pbitónico en hipercubo: n ∝ 2^(log² p)Hyksort: n log n ∝ p log² p

Bitónico · mallan ≈ 2^32.0

Bitónico · hipercubon ≈ 2^1.0e+2

Hyksortn ≈ 2^12.9

Con p = 2^10: √p = 32.0 < log²p = 100, así que la malla necesita menos datos que el hipercubo (esta es la respuesta de la PD5). Hyksort necesita muchísimo menos que ambos: crece de forma polinomial, no exponencial.

PD05, ejercicio 3b: Hyksort (0.5 pts)

Enunciado: T_p = O((n/p)·log n + log p·(n/p) + log² p). ¿Escala mejor que los anteriores?

Resolución paso a paso

• p·T_p = n log n + n·log p + p·log² p
• T_o = n·log p + p·log² p

Se iguala W = K·T_o término a término (el término que pida más n manda):

1. n log n ∝ n log p ⇒ log n ∝ log p ⇒ n ∝ p^K (polinomial)
2. n log n ∝ p log² p ⇒ n ≈ p log p (polinomial). Esta es la que da la PD: “n log n ∝ p log²(p)”.

Las dos son polinomiales, mientras que el bitónico pide crecimiento exponencial (2^√p o 2^{log² p}). Por tanto Hyksort escala mucho mejor que los anteriores.

Ejemplo numérico con p = 1024: el bitónico en malla pide n ≈ 2³² ≈ 4·10⁹ datos (con K = 1); Hyksort pide n ≈ p log p ≈ 10⁴.

Tabla resumen (lámina 36, reconstruida)

La lámina 36 tiene las celdas desalineadas. Esta es la lectura coherente con las láminas anteriores y con la PD:

Algoritmo	Secuencial	Span (p = n)	Con p procesos (Brent / bloques)
Bubble sort (odd-even transposition)	O(n²)	O(n)	O(n²/p + p)
Mergesort	O(n log n)	O(n) si la mezcla es secuencial · O(log² n) con odd-even merge	—
Quicksort	O(n log n) promedio	O(log² n)	O((n/p) log n + log² p)
Bitónico	O(n log n) (mejor secuencial)	O(log² n)	O((n/p) log n + log² p)
Heapsort	O(n log n)	difícil de paralelizar	—

Las dos ideas finales de la lámina:

• Con n > p, el cómputo local (n/p) log(n/p) importa: es la parte que se reparte bien.
• Hay que minimizar la comunicación, porque es lo que decide la escalabilidad (en el ejemplo de ranking dominaba ×65). La lámina 37 (Axtmann & Sanders 2020, 262 144 núcleos) muestra que el mejor algoritmo cambia según n/p.

Práctica

1. Un ordenamiento tiene T_p = (n/p) log n + log² p. ¿Cuál es su isoeficiencia?

Ver solución

T_o = p·T_p − n log n = p log² p. Con W = K·T_o: n log n ∝ p log² p ⇒ n ∝ p log p. Es muy escalable: duplicar p pide algo más del doble de datos.

2. Con E = 0.8, ¿cuánto vale K? Para el bitónico en hipercubo con p = 64, ¿qué n hace falta?

Ver solución

K = E/(1 − E) = 0.8/0.2 = 4.

Hipercubo: log n = K·log² p = 4 · 6² = 144, así que n = 2¹⁴⁴, un número imposible. Mantener E = 0.8 con el bitónico es inviable aunque p sea pequeño: en la práctica se acepta una E menor. Con K = 1 (E = 0.5): log n = 36, n = 2³⁶ ≈ 6.9·10¹⁰, que sigue siendo enorme.

Errores típicos

• Usar W = n para un ordenamiento. El mejor secuencial por comparaciones es n log n.
• Restar W de T_p en vez de p·T_p: el overhead es p·T_p − W.
• Comparar dos isoeficiencias exponenciales sin fijar el rango de p: aquí el ganador cambia en p = 2¹⁶.
• Olvidar la constante K = E/(1 − E): no cambia el orden de crecimiento, pero sí el valor de n.

Autoevaluación

0/5 correctas · 0 respondidas Reiniciar

1. El overhead se define como…

a) T_p − T_sb) p·T_p − T_sc) T_s/T_pd) p/T_p

2. Isoeficiencia del bitónico en malla:

a) n ∝ pb) n ∝ p log pc) n ∝ 2^√pd) n ∝ 2^(log² p)

3. Según la PD5, ¿qué topología escala mejor para el bitónico (p prácticos)?

a) hipercubob) mallac) igualesd) ninguna

4. ¿Desde qué p el hipercubo pasa a escalar mejor que la malla?

a) p > 16b) p > 1024c) p > 2^16d) nunca

5. Hyksort escala mejor porque su isoeficiencia es…

a) exponencialb) polinomialc) constanted) logarítmica

Fuente ·2026I-CS4052-PD5.pdf (ejercicio 3) · U5.2 Algoritmos-ordenamiento.pdf (láminas 21, 36–37) · U2.1 Diseño en paralelo-performance (isoeficiencia)