N-Body, Divide y Vencerás, Mergesort y matrices

N-Body

$$F_i=-Gm_i\sum_{j\ne i}\frac{m_j\,r_{ij}}{|r_{ij}|^3}\qquad v_{t+1}=v_t+\frac{F\Delta t}{m}\qquad x_{t+1}=x_t+v\Delta t$$

• $N(N-1)/2$ pares ⇒ $O(N^2)$ por paso. Sin solución analítica desde $N=3$. La integración por intervalos es aproximada (se mejora con leap-frog).
• Paralelo directo: cada proceso un subgrupo de cuerpos ⇒ $O\!\left(\frac{n(n-1)}{p}\right)$.
• Barnes-Hut: un cluster lejano se aproxima como un solo cuerpo (quadtree/octree) ⇒ $O(n\log n/p)$.
• Compartida (OpenMP/CUDA): sin comunicación, limitada por los núcleos de un nodo. Distribuida (MPI): paga comunicación pero escala el cluster.
• $T_{total}=T_{cómputo}\downarrow+T_{comm}\uparrow$ ⇒ existe un $p$ óptimo; con más cuerpos se desplaza a más procesadores (ver FLOPs).

N-Body: simulación all-pairs repartida entre procesos

Color = proceso dueño del cuerpo (bloques de n/p). Cada paso: cada proceso calcula la fuerza sobre sus cuerpos usando los n−1 restantes ⇒ necesita las posiciones de todos (Allgather).

cuerpos n = 64procesos p = 4⏸︎ Pausa↻ Reiniciar mostrar interacciones de un cuerpo

pasos simulados0

cuerpos por proceso≈ 16

interacciones / paso (total)4032

por proceso1010

posiciones recibidas / proceso48

p óptimo (modelo)28

t por interacción = 1e-7 sα latencia = 1e-5 s

T_cómputo = n(n−1)/p · tT_comm = α log p + β nT_total

Con p=4: cómputo 1.01e-4 s, comunicación 4.05e-5 s. $O\!\left(\tfrac{n(n-1)}{p}\right)$ baja con p, la comunicación sube ⇒ hay un p óptimo, que se desplaza a la derecha si n crece (sube n y mira la línea verde). Barnes-Hut reduce el cómputo a $O(n\log n/p)$.

Divide y Vencerás

Dividir en subproblemas de tamaño $n/b$ → vencer (caso base o recursión) → combinar. En paralelo, ramas distintas del árbol de recursión corren a la vez (pardo); típicamente $n/p$ datos por proceso y combinación en el maestro.

Mergesort paralelo

MergeSort-Paralelo(A, n):
  if n > 1:
    m ← ⌊n/2⌋
    pardo:
      MergeSort-Paralelo(A[1..m], m)
      MergeSort-Paralelo(A[m+1..n], n-m)
    Merge(A, n)          // secuencial, O(n)

$$W(n)=2W(n/2)+O(n)=O(n\log n)\qquad T_\infty(n)=T_\infty(n/2)+O(n)=O(n)$$ $$T_p=O\!\left(\frac{n\log n}{p}+n\right)\qquad S=O\!\left(\frac{n\log n}{\frac{n\log n}{p}+n}\right)\qquad E=O\!\left(\frac{1}{1+\frac{p}{\log n}}\right)$$

Mergesort paralelo: árbol de recursión animado

Baja dividiendo (O(1) por nivel) y sube combinando. Las dos llamadas recursivas van en pardo; el merge decide el span.

n = 8procesos p = 4

Merge secuencial O(n)Merge paralelo O(log n)

🎲 Otro arreglo

⏮︎◀︎▶︎ Play▶︎⏭︎

0.5×1×2×4×

paso 0/6

faseinicio

trabajo de merge acumulado0 ops

span acumulado (secuencial)0

span total (n=8)≈ 2n = 16

$T_\infty(n)=T_\infty(n/2)+O(n)=O(n)$: el último merge (n elementos) lo hace un solo procesador ⇒ cuello de botella. Con n=10⁶ y p=4: $T_p=O\!\left(\tfrac{n\log n}{p}+n\right)$ ≈ 6.98e6 ⇒ S ≈ 2.85 (tope $\log n$ ≈ 19.9).
En ambos casos $W(n)=2W(n/2)+O(n)=O(n\log n)$. Los colores de borde muestran qué proceso tiene cada bloque (n/p elementos por proceso).

Error común

Sumar las dos ramas en el span: $T_\infty(n)=2T_\infty(n/2)+\dots$ ✗. Las ramas corren en paralelo ⇒ el span «ve» solo una: $T_\infty(n)=T_\infty(n/2)+\dots$ ✓. El trabajo sí suma ambas.

En el examen…

El Merge secuencial $O(n)$ es el cuello de botella del span. Con un merge paralelo en $O(\log n)$ el span baja a $O(\log^2 n)$ («optimizable»). Mismo patrón: quicksort con prefix sum ⇒ $T_\infty=T_\infty(n/2)+O(\log n)=O(\log^2n)$.

Multiplicación de matrices (expansión + reducción)

for 1≤i,j,k≤n pardo          C'(i,j,k) ← A(i,k)·B(k,j)        // expansión: n³ productos
for h=1 to log n do
  for 1≤i,j≤n, 1≤k≤n/2^h pardo
                             C'(i,j,k) ← C'(i,j,2k-1)+C'(i,j,2k)  // reducción en árbol
for 1≤i,j≤n pardo            C(i,j) ← C'(i,j,1)

$W=O(n^3)$, $T_\infty=O(\log n)$, $T_p=O(n^3/p+\log n)$: una reducción binaria replicada $n^2$ veces. (Contrasta con el arquetipo F, acceso directo sin árbol, $T_\infty=O(n)$.)

Multiplicación de matrices en paralelo

Arquetipo F: ¿EREW o CREW?Expansión + reducción (DAG)

k' = (i+j+k) mod n (PD02 2026-I)k' = k (bucle ingenuo)

n = 4

⏮︎◀︎▶︎ Play▶︎⏭︎

0.5×1×2×4×

k 0/4

Haz clic en una celda de C para seguir a ese procesador P(i,j). Verde = celda leída por 1 procesador; rojo = lectura concurrente.

P(1,2) en paso k=——

máx. lectores de una celda—

escrituras en C[i,j]solo P(i,j)

modelo mínimo—

Con el índice rotado, en cada paso los n² procesadores leen n² celdas distintas de A y de B, y cada uno escribe solo su C[i,j] ⇒ EREW. Fila i fija: j distinto ⇒ columna (i+j+k) mod n distinta.
$T_s=O(n^3)t_c,\quad T_p=O\!\left(\tfrac{n^3}{p}t_c+n\right),\quad E=\tfrac{1}{1+\frac{p}{t_cn^2}}$ ⇒ débil: escala si $n\propto\sqrt p$.

Playground: teorema maestro

Recurrencias Divide y Vencerás — Teorema maestro

$T(n)=a\,T(n/b)+f(n),\quad f(n)=\Theta(n^k\log^j n)$ — compara $n^{\log_b a}$ (hojas) con f(n) (raíz).

a (subproblemas) = 2b (factor de división) = 2k (exponente de n en f) = 1j (potencia de log en f) = 0

$$T(n)=2\,T\!\left(\tfrac{n}{2}\right)+\Theta\!\left(n\right),\qquad \log_{2}2=1$$

Caso2

Resultado$T(n)=\Theta\left(n\,\log n\right)$

Caso 2: f(n) y n^{log_b a} crecen igual ⇒ cada uno de los log n niveles cuesta lo mismo: se multiplica por un log n extra.

Costo por nivel del árbol de recursión (n = 2^10)

Recurrencias “por resta” (no son del teorema maestro): $T(n)=T(n-1)+O(n)\Rightarrow\Theta(n^2)$ · $T(n)=T(n-1)+O(1)\Rightarrow\Theta(n)$ · Fibonacci $W(n)=W(n-1)+W(n-2)+1$ ⇒ exponencial, $T_\infty(n)=T_\infty(n-1)+1\Rightarrow\Theta(n)$.

Ejercicio (PD02 2026-I, Ej. 2): búsqueda de $m$ elementos en un árbol 2-3

Árbol 2-3: nodos internos con 2 o 3 hijos, hojas a la misma profundidad, ordenado. (2.1) PRAM y span. (2.2) $W$, $T_\infty$. (2.3) $T_p$, $S$, $E$. (2.4) Escalabilidad.

Ver solución

for i ← 1 to m pardo
    R[i] ← busqueda23(T.raiz, Q[i])     // recursiva: baja un nivel por llamada

$$W(h,m)=W(h-1,m)+O(m)=O(mh)=O(m\log n)\qquad T_\infty(h)=T_\infty(h-1)+O(1)=O(h)=O(\log n)$$

Las $m$ búsquedas son independientes: el span es el de una búsqueda.

$$T_p=O\!\left(\frac{m\log n}{p}+\log n\right)\quad S=O\!\left(\frac{m\log n}{\frac{m\log n}{p}+\log n}\right)\quad E=O\!\left(\frac{1}{1+\frac pm}\right)$$

Fuerte ($m$ cte): $E=O(1/p)$, no escala. Débil: $E=O(1)$ si $p\propto m$.

Ejercicio (PD02 2025-I, Ej. 3): quicksort paralelo con suma de prefijos

Cada elemento es asignado a un proceso (memoria compartida); en cada nivel se elige pivote, se marca $f_i=[d_i\le v]$ y la posición se obtiene con suma de prefijos. (a) $W$, $T_\infty$, $T_p$, $S$, $E$, escalabilidad. (b) Agregue comunicación colectiva $T(p)=O(\log p)$.

Ver solución

(a) $W=T_s=O(n\log n)$; $T_\infty(n)=T_\infty(n/2)+O(\log n)=O(\log^2n)$; $T_p=O\!\left(\frac{n\log n}{p}+\log^2n\right)$, $E=\dfrac{1}{1+\frac{p\log n}{n}}$ ⇒ escala si $p\propto n/\log n$.

(b) $T_p=O\!\left(\frac{n\log n}{p}+\log^2n+\log p\right)$, $E=\dfrac{1}{1+\frac{p\log n}{n}+\frac{p\log p}{n\log n}}$ ⇒ dos condiciones: $p\propto n/\log n$ y $p\log p\propto n\log n$; la segunda es la dominante.

Autoevaluación

0/5 correctas · 0 respondidas Reiniciar

1. $T(n)=2T(n/2)+O(n)$ ⇒

a) $\Theta(n)$b) $\Theta(n\log n)$c) $\Theta(n^2)$d) $\Theta(\log n)$

2. Span del mergesort paralelo con merge secuencial:

a) $O(\log n)$b) $O(\log^2 n)$c) $O(n)$d) $O(n\log n)$

3. Barnes-Hut reduce N-Body a…

a) $O(n^2/p)$b) $O(n\log n/p)$c) $O(n/p)$d) $O(\log n)$

4. Operaciones de fuerza por paso en N-Body directo:

a) $N$b) $N(N-1)/2$c) $N\log N$d) $N^3$

5. Span de la multiplicación de matrices por expansión+reducción:

a) $O(1)$b) $O(\log n)$c) $O(n)$d) $O(n^3)$

Fuente ·estudio/07_NBody_DivideVenceras.md · U2.5-Diseño_en_paralelo-NBody-DivideYVenceras.pdf · previos/2026-I (Ej. 2) · previos/2025-I (Ej. 3) · P1.md