Repartir el árbol: PWS, DTS y clusters

💡 En simple

Hay dos formas de que un equipo busque un objeto perdido en un edificio:

• DTS (repartir el edificio): cada persona revisa pisos distintos con el mismo cuidado. No se repite nada, pero si a alguien le toca el piso más grande, todos lo esperan.
• PWS (repartir el nivel de detalle): todos recorren el edificio entero, pero cada uno con una “lupa” distinta: uno mira solo por encima, otro un poco más, otro a fondo. Se repite mucho trabajo, pero sirve cuando no sabes qué tan escondido está el objeto.

Los clusters mezclan las dos: varios equipos, cada equipo con su lupa, y dentro del equipo se reparten los pisos.

Descomposición del dominio (láminas 24–26)

Se parte el espacio de búsqueda (el árbol) y cada procesador busca en sus subárboles a la vez. El problema: los subárboles pueden tener tamaños muy distintos y es difícil saberlo antes de explorarlos. Por eso suele hacer falta balance de carga dinámico (ver la página de balance).

Caso p = b^k. Si el factor de ramificación es b, se elige un nivel k con b^k = p nodos. La búsqueda hasta el nivel k es secuencial (hay que generar esos nodos), y desde ahí cada proceso busca su subárbol de profundidad d − k:

$$T_p = O\big(\underbrace{b^k}_{\text{generar la frontera}} + \underbrace{b^{d-k}}_{\text{un subárbol}}\big)$$

Cómo leerlo: a la izquierda, la parte gris (hasta el nivel k) la hace un solo proceso; debajo, cada triángulo es el subárbol de un proceso. Si el árbol está balanceado, todos terminan juntos. A la derecha, el árbol no está balanceado: se corta más profundo para tener muchos subárboles pequeños y repartir varios por proceso, así los grandes y los chicos se compensan (lámina 26).

Práctica: b = 3, d = 10, p = 9

k = log₃ 9 = 2. T_p = O(3² + 3⁸) = O(9 + 6561) ≈ 6570 nodos frente a T_s ≈ 3¹⁰ = 59 049. S ≈ 59 049 / 6570 ≈ 9, E ≈ 1: con árbol balanceado la parte secuencial (9 nodos) es despreciable.

Parallel Window Search, PWS (láminas 27–28)

Powley y Korf (1991). Cada proceso recibe una copia completa del árbol y un umbral de costo distinto (su “ventana”). Cada uno hace un DFS limitado (como una ronda de IDA*) en paralelo. Hay que esperar a que todos terminen para saber el resultado.

B ← h(s);  solución ← ∅
while solución = ∅:
    for i ← 0 .. p−1 pardo:
        B_i ← B + i·Δ
        (sol_i, c_i, next_i) ← DFSLimitado(s, B_i)
    TASKWAIT()
    S ← { sol_i ≠ ∅ }
    if S ≠ ∅: return la de menor c_i
    B ← mín_i next_i          // nueva ronda con umbrales más altos

Idea clave: IDA* secuencial prueba los umbrales B, B + Δ, B + 2Δ… uno tras otro. PWS los prueba todos a la vez, uno por proceso. Si la solución está en el umbral B + 5Δ, el secuencial hace 6 rondas; PWS con p ≥ 6 hace una sola.

Costo: los procesos repiten la parte alta del árbol (trabajo redundante). PWS solo gana si de verdad ahorra rondas.

Distributed Tree Search, DTS (láminas 29–30)

Kumar y Rao (1990). Todos los procesos usan el mismo umbral, pero cada uno recibe un subárbol distinto. Hay que fijar el nivel de partición; hasta ese nivel el cálculo es secuencial.

k ← log_b p
F ← GenerarFrontera(s, k, B)          // secuencial: b^k nodos
for i ← 0 .. |F|−1 pardo:
    (sol_i, c_i, next_i) ← DFSLimitado(F[i], B)
TASKWAIT()
return la sol de menor c_i, y next = mín next_i

Sin trabajo redundante, pero el tiempo lo fija el subárbol más grande.

Búsqueda adaptiva por clusters (lámina 31)

Cook (1997). Los p procesos se agrupan en clusters. Cada cluster tiene su umbral (como PWS) y dentro del cluster se reparte el árbol (como DTS).

• 1 cluster con p procesos = DTS.
• p clusters de 1 proceso = PWS.

Cómo leerlo: en PWS cada proceso tiene el árbol entero (gris) y su parte coloreada llega hasta su umbral B + iΔ: las partes de arriba se solapan, eso es trabajo repetido. En DTS el árbol se corta en franjas de colores, todas hasta el mismo umbral B. En clusters, cada triángulo es un cluster con su propio umbral, repartido entre sus 3 procesos.

Complejidades (lámina 32)

Método	T(n, p)	E(n, p)
DTS	O(bd/p + bk + log p)	O( 1 / (1 + (p·bk + p·log p) / bd) )
PWS	O(bd/p + bm + log p)	O( 1 / (1 + (p·bm + p·log p) / bd) )
Clusters	O(bd/p + bk + bm + log p)	O( 1 / (1 + p·(bk + bm + log p) / bd) )

Qué es cada término:

• b^d/p: el trabajo útil (el árbol) repartido.
• b^k: generar la frontera hasta el nivel de partición k, en secuencia (DTS).
• b^m: la parte que se repite por el umbral/ventana m (PWS). Lectura propia: la lámina no define m; en la participación 9 los umbrales también se llaman m.
• log p: juntar los resultados al final (el TASKWAIT y quedarse con el mínimo es una reducción).

Las tres eficiencias tienen la misma forma que vimos en el parcial: E = 1 / (1 + overhead/trabajo). Se mantiene alta mientras b^d (el árbol) crezca más rápido que p·(overhead).

Cuándo usar cada uno (lámina 32):

Método	Bueno para…	Por qué
DTS	árboles bien balanceados	no repite trabajo; si los subárboles son parejos, todos terminan juntos
PWS	búsquedas heurísticas profundas (IDA* con muchas rondas)	ahorra rondas; la repetición pesa poco frente a lo que ahorra
Clusters	máquinas multinodo	combina ambas ventajas: PWS entre nodos, DTS dentro

Performance: depende de dónde está la meta (lámina 33)

Cook y Varnell (1998), con p = 10, b = 6, d = 10. Sea a la fracción de nodos que hay que expandir (en la última ronda) antes de encontrar la solución. El speedup de PWS es aproximadamente:

$$S_\text{PWS} = 1 + \frac{1}{a\,(b-1)}$$

• Si la meta aparece pronto (a pequeño), PWS gana mucho: con a = 0.05 y b = 6, S = 1 + 1/0.25 = 5.
• Si aparece tarde (a → 1), S → 1 + 1/5 = 1.2: casi no gana.
• En la figura de la lámina, la curva de PWS cae suavemente al moverse la meta a la derecha, mientras que la de DTS tiene picos: DTS gana mucho cuando la meta cae al principio del subárbol de algún proceso (ese proceso la encuentra enseguida) y poco en el resto.

Conclusión práctica: ninguno domina siempre. Depende de la forma del árbol y de dónde esté la solución, y eso no se sabe antes de buscar.

Simulador: el árbol de la participación 9

Prueba los cuatro modos. Fíjate en tres cosas: (1) cuánto tarda el último proceso, (2) cuántas aristas se repiten, (3) cuánto tiempo pasa ocioso cada proceso en el diagrama de abajo.

Búsqueda en el árbol de la participación 9: secuencial, PWS y DTS

Un paso = recorrer una arista. Cada color es un proceso. Dale Play y mira quién trabaja en cada paso, dónde aparece cada solución y cuándo termina el último proceso.

Secuencial (DFS)PWS (m = 1, 2, 3)DTS (corte en m = 1)DTS (cortes en m = 1 y m = 2)

⏮︎◀︎▶︎ Play▶︎⏭︎

0.5×1×2×4×

paso 0/13

T_p (último proceso)13 pasos

Trabajo hasta ahora0 aristas

Redundante0

S = 35 / T_p2.69

E = S / p (p = 6)0.45

s1aún no

s2aún no

s3aún no

Dos momentos de partición (3 + 2 pasos) y 6 búsquedas locales. Manda el subárbol a1 (8 aristas): 5 + 8 = 13. P5 recibe directamente s3 y no tiene nada que buscar.

La resolución completa, con todas las tablas, está en Participación 9 resuelta.

Errores típicos

• Decir que PWS reparte el árbol: no, cada proceso tiene el árbol completo; lo que se reparte son los umbrales.
• Olvidar el tramo secuencial hasta el nivel k en DTS (b^k).
• Calcular el tiempo de DTS como trabajo/p: el tiempo es el del subárbol más grande, no el promedio.
• Dar por hecho que más procesos en DTS siempre mejoran la eficiencia: partir más profundo aumenta p pero también el desbalance y el tramo secuencial.

Autoevaluación

0/7 correctas · 0 respondidas Reiniciar

1. En PWS, cada proceso recibe…

a) un subárbol distinto con el mismo umbralb) una copia del árbol con un umbral de costo distintoc) un nivel del árbold) una lista de hojas

2. En DTS, ¿qué parte es secuencial?

a) ningunab) la búsqueda en las hojasc) generar la frontera hasta el nivel de partición kd) el TASKWAIT

3. Con b = 2 y p = 8 procesos en DTS, el nivel de partición es…

a) k = 2b) k = 3c) k = 4d) k = 8

4. ¿Qué método repite trabajo?

a) DTSb) PWSc) ningunod) los dos por igual

5. ¿Cuál conviene para un árbol muy balanceado y un umbral conocido?

a) PWSb) DTSc) búsqueda lineald) clusters con p clusters

6. p clusters de 1 proceso cada uno equivale a…

a) DTSb) PWSc) DFS secuenciald) B&B

7. S_PWS = 1 + 1/(a(b−1)). Con a = 0.1 y b = 3, S =

a) 1.5b) 6c) 3d) 1.05

Fuente ·U5.3 Algoritmos-busqueda.pdf (láminas 24–33)