PRÁCTICA 2A: REPORTE ESCRITO. EXPERIMENTOS Y ANÁLISIS DE ESTRUCTURAS DE DATOS¶

PROFESOR: DR. ERIC SADIT TÉLLEZ AVILA

ESTUDIANTE: EDGAR SANTIAGO GONZALEZ MARTINEZ

Introducción¶

Dadas matrices de consultas y candidatos, trabajaremos con:

$$ Q \in \mathbb{R}^{d\times m}, \qquad X \in \mathbb{R}^{d\times n}. $$

Para cada columna de $Q$ buscamos el vector de $X$ que maximiza el producto punto:

$$ j^{*}(i) \;=\; \arg\max_{1\le j\le n}\; q_i^{\top}x_j, \qquad s_i \;=\; \max_{1\le j\le n}\; q_i^{\top}x_j . $$

Cuando las columnas están normalizadas, el producto punto coincide con la similitud coseno y el problema equivale a encontrar el vecino más similar de $q_i$ en $X$ (Golub & Van Loan, 2013). Definimos la matriz de similitudes:

$$ S \;=\; Q^{\top}X \;\in\; \mathbb{R}^{m\times n}. $$

El coste aritmético total viene dado por:

$$ \mathrm{flops}_{\mathrm{tot}} \;=\; (2d-1)\,m\,n . $$

En la práctica hay un compromiso tiempo–memoria: materializar $S$ (rápido, pero requiere memoria $O(mn)$) o procesar por lotes (menos memoria, más pasadas) (Dongarra, Du Croz, Duff, & Hammarling, 1990; Harris et al., 2020). Como línea base pedagógica consideramos una versión con bucles explícitos (mydot/getmaxdot); además comparamos variantes vectorizadas por columna y una versión matricial completa.

En este trabajo evaluamos cinco enfoques:

  • A0: bucles mydot/getmaxdot (línea base).
  • A1-naive y A1-adapt: vectorización por columna.
  • A2: materializa $S=Q^{\top}X$.
  • A3: procesamiento por lotes con presupuesto de memoria.

Los experimentos usan 9 combinaciones y datos normalizados:

$$ d=8, \qquad m,n \in \{10^3,\;10^4,\;10^5\}. $$

Reportamos tiempo real, memoria pico aproximada y flops teóricos, y discutimos cuándo conviene cada enfoque bajo restricciones de memoria (Golub & Van Loan, 2013; Harris et al., 2020).

Limitaciones¶

  • Recursos de hardware: las corridas se realizaron en equipo local (Jupyter) y en Google Colab. En instancias grandes, A2-full se omite cuando $S$ no cabe en memoria; en esos casos se recurre a A3-batched con tamaño de lote ajustado al presupuesto.
  • Pico de memoria: la memoria de $S$ crece como $m\,n\,\text{bytes}$ (con float32, 4 B/elem). Para combinaciones extremas (p. ej., $10^5 \times 10^5$) se requerirían muchos GB, por encima del límite práctico; por eso A2 no se ejecuta ahí.
  • Tiempo de ejecución: para problemas muy grandes, incluso con A3, los tiempos pueden ser prohibitivos por el número de pasadas $\lceil m/b\rceil$. Para evitar corridas interminables se aplican políticas que reducen repeticiones y restringen tamaños.
  • Interpretación de resultados: las comparaciones deben leerse condicionadas por estos límites; con más memoria o distinto hardware, la cobertura y los tiempos pueden variar.

Importaciones y parámetros¶

Antes de iniciar, importamos las librerías necesarias. Usamos NumPy (numpy as np) para el cálculo numérico y las operaciones de álgebra lineal (vectores, matrices y el operador @), y Pandas (pandas as pd) para registrar los resultados en tablas y exportarlos a CSV. Además, traemos time para cronometrar las funciones y medir tiempo real, gc para forzar la recolección de basura y liberar memoria entre corridas grandes, y re para leer de forma sencilla el archivo /proc/meminfo cuando necesitamos estimar la memoria disponible. Con Path de pathlib gestionamos rutas de forma portable, y display de IPython.display nos ayuda a mostrar DataFrames con buen formato dentro del notebook.

In [62]:
# Importaciones de librerias
import numpy as np
import pandas as pd
import math, time, gc, re
from pathlib import Path
from IPython.display import display

Fijamos después los parámetros base del experimento. Para que los resultados sean reproducibles, iniciamos un generador aleatorio con rng = np.random.default_rng(286). En este estudio trabajamos con dimensión d = 8 y con un conjunto de tamaños grid = [10**3, 10**4, 10**5]. De esta forma generamos las 9 combinaciones $(m,n)$ requeridas.

In [63]:
# Semilla y parámetros base
rng = np.random.default_rng(286)
d = 8
grid  = [10**3, 10**4, 10**5]
dtype = np.float32

Para evitar errores de memoria y definir un marco de comparación justo, establecemos límites claros. El parámetro A2_MEM_LIMIT_MB = 9000 marca el tamaño máximo permitido (en MB) para materializar la matriz de similitudes $S = Q^{\top} X$ en el algoritmo A2; si $m \cdot n$ multiplicado por los bytes del tipo excede ese umbral, A2 se salta de forma segura. El parámetro MEM_BUDGET_MB = 6000 fija el presupuesto de memoria por lote en el algoritmo A3; a partir de este valor se calcula automáticamente un tamaño de lote b que mantiene el pico en torno a $b \cdot n \cdot \text{bytes}$.

In [64]:
# Límites de memoria
MEM_BUDGET_MB   = 6000
A2_MEM_LIMIT_MB = 9000

También definimos una política para las variantes más lentas, de forma que en la ejecución no se tarde muchas horas e incluso días. La versión con bucles puros A0 (mydot/getmaxdot) solo se ejecuta si el número de pares $m \cdot n$ es menor o igual a 100_000_000; la variante A1-adapt comparte ese umbral. La versión A1-naive se permite hasta 200_000_000 pares. Además, cuando el problema es verdaderamente grande (REPEAT_LARGE_THRESHOLD_PAIRS = 800_000_000), el benchmark reduce a 1 el número de repeticiones para ahorrar tiempo de ejecución.

In [65]:
A0_LOOPS_MAX_PAIRS   = 100_000_000
A1_ADAPT_MAX_PAIRS   = 100_000_000
A1_NAIVE_MAX_PAIRS   = 200_000_000
REPEAT_LARGE_THRESHOLD_PAIRS = 800_000_000

Por otra parte, se añade guard-rails dinámicos basados en la memoria libre real del sistema. El parámetro A2_FRAC_FREE = 0.60 obliga a que A2 solo se ejecute si, además de respetar el límite fijo, (S) no supera el 60 % de la RAM disponible en ese momento. De forma análoga, A3_FRAC_FREE = 0.30 limita el presupuesto efectivo por lote de A3 al 30 % de la memoria libre. Para medir dicha memoria libre utilizamos la función ram_disponible_mb(), que intenta leerla con psutil y, si no está disponible, consulta /proc/meminfo. Esta función devuelve la RAM libre en MB o None cuando no puede estimarla; en ese caso, el cuaderno recurre únicamente a los límites fijos. Al terminar la configuración imprimimos un breve resumen (dtype activo, límites fijados y RAM libre estimada) para decidir, si hiciera falta, si conviene relajar o apretar los umbrales antes de ejecutar los casos grandes.

In [66]:
A2_FRAC_FREE = 0.60
A3_FRAC_FREE = 0.30
def ram_disponible_mb():
    try:
        import psutil
        return psutil.virtual_memory().available / 1e6
    except Exception:
        try:
            with open('/proc/meminfo') as f:
                txt = f.read()
            m = re.search(r"MemAvailable:\s+(\d+)\s+kB", txt)
            return (int(m.group(1))/1024.0) if m else None
        except Exception:
            return None
print('dtype =', np.dtype(dtype).name)
print('A2_MEM_LIMIT_MB =', A2_MEM_LIMIT_MB, '| MEM_BUDGET_MB =', MEM_BUDGET_MB)
avail = ram_disponible_mb()
print('RAM libre (estimada):', f"{avail:,.0f} MB" if avail else '¿N/D?')

dtype = float32
A2_MEM_LIMIT_MB = 9000 | MEM_BUDGET_MB = 6000
RAM libre (estimada): 11,836 MB

Algoritmos¶

A0
Esta es la línea base: mydot(u, x) acumula el producto punto elemento a elemento en un bucle; getmaxdot(u, X) busca el índice j que maximiza $u^\top x_j$ recorriendo todas las columnas de $X$; y maxdot_loops(Q, X) aplica lo mismo a cada columna $q_i$ de $Q$. Es correcto y de memoria $O(1)$, pero muy lento por la sobrecarga de bucle interpretado.

In [67]:
def mydot(u, x):
    s = 0.0
    for i in range(len(u)):
        s += float(u[i]) * float(x[i])
    return s
def getmaxdot(u, X):
    maxpos = 0
    maxdot = mydot(u, X[:, 0])
    for j in range(1, X.shape[1]):
        dval = mydot(u, X[:, j])
        if dval > maxdot:
            maxpos = j
            maxdot = dval
    return maxpos, maxdot
def maxdot_loops(Q, X):
    d, m = Q.shape
    idx  = np.empty(m, dtype=np.int64)
    vals = np.empty(m, dtype=Q.dtype)
    for i in range(m):
        j, v = getmaxdot(Q[:, i], X)
        idx[i]  = j
        vals[i] = v
    return idx, vals

A1 — Vectorizado por columna (maxdot_naive, getmaxdot_many).
Estas dos variantes recorren las columnas de $Q$, pero cada producto $q_i^\top X$ se calcula con operaciones vectorizadas de NumPy. Así, el “bucle caro” vive en código nativo: es mucho más rápido que A0, manteniendo un pico de memoria $O(n)$.

In [68]:
def maxdot_naive(Q, X):
    m = Q.shape[1]
    idx = np.empty(m, dtype=np.int64)
    val = np.empty(m, dtype=Q.dtype)
    for i in range(m):
        s = Q[:, i].T @ X
        j = np.argmax(s)
        idx[i], val[i] = j, s[j]
    return idx, val
def getmaxdot_many(Q, X):
    m = Q.shape[1]
    idx = np.empty(m, dtype=np.int64)
    val = np.empty(m, dtype=Q.dtype)
    for i in range(m):
        s = Q[:, i].T @ X
        j = np.argmax(s)
        idx[i], val[i] = j, s[j]
    return idx, val

A2 — Matriz completa de similitudes (maxdot_full).
En este codigo computa de una sola vez $S = Q^\top X \in \mathbb{R}^{m\times n}$ mediante una multiplicación matricial, y luego toma el argmax por filas. Es típicamente el más rápido en tiempo de cómputo porque explota al máximo el backend numérico, pero exige memoria $O(mn)$ para materializar $S$.

In [69]:
def maxdot_full(Q, X):
    S = Q.T @ X
    idx = np.argmax(S, axis=1)
    val = S[np.arange(S.shape[0]), idx]
    return idx, val

A3 — Procesamiento por lotes (safe_batch, maxdot_batched).
Para casos grandes donde A2 no cabe, dividimos $Q$ en bloques de tamaño $b$ y procesamos submatrices $Q_{[:, i_0:i_1]}^\top X$. La función safe_batch(n, …) fija $b$ a partir de un presupuesto en MB y del tamaño del tipo (dtype), de modo que el pico quede acotado por: $$ \text{pico} \;\approx\; b \cdot n \cdot \text{bytes\_por\_elemento}. $$ A3 usa memoria $O(bn)$ y requiere $\lceil m/b \rceil$ pasadas. Es exacto, pero puede tardar más si el número de pasadas es grande.

In [57]:
def safe_batch(n, dtype=np.float32, mem_budget_mb=1000):
    bytes_per = bytes_per_dtype(dtype)
    max_batch = int(max(1, (mem_budget_mb*1_000_000)//(n*bytes_per)))
    return max(1, max_batch)
def maxdot_batched(Q, X, batch=1000):
    m = Q.shape[1]
    idx = np.empty(m, dtype=np.int64)
    val = np.full(m, -np.inf, dtype=Q.dtype)
    for i0 in range(0, m, batch):
        i1 = min(i0 + batch, m)
        Sb = Q[:, i0:i1].T @ X   # (bi, n)
        ib = np.argmax(Sb, axis=1)
        vb = Sb[np.arange(Sb.shape[0]), ib]
        idx[i0:i1], val[i0:i1] = ib, vb
    return idx, val

Evaluación¶

Esta función ejecuta y mide todas las variantes (A0–A3) para una pareja de tamaños $(m,n)$. Primero genera dos matrices con columnas normalizadas: $Q \in \mathbb{R}^{d\times m}$ y $X \in \mathbb{R}^{d\times n}$ (make_matrix). Después calcula el trabajo teórico en flops, usando $\text{flops}_{\text{tot}} = (2d-1)\,m\,n$, y prepara un contenedor results donde irá registrando, por algoritmo, tiempo, memoria pico aproximada y flops.

La política de repetición repeats_for(m,n) controla la duración del benchmark: si el problema es muy grande, usa repeat = 1 para no alargar la ejecución; en tamaños moderados usa repeat = 2 (promedio de dos mediciones tras un warm-up en bench).

En esta parte se evalúan las variantes:

  • A0-loops. Ejecuta la línea base con bucles puros (maxdot_loops) solo si $m\cdot n \le$ A0_LOOPS_MAX_PAIRS. Es correcta y de memoria $O(1)$, pero lenta; por eso se restringe a tamaños pequeños (time_s queda None si se omite). La memoria pico reportada es 0 porque no materializa buffers grandes.

  • A1-naive y A1-adapt. Son versiones vectorizadas por columna que aprovechan BLAS. Se ejecutan si $m\cdot n$ está por debajo de los umbrales A1_NAIVE_MAX_PAIRS y A1_ADAPT_MAX_PAIRS, respectivamente. También reportan mem_MB = 0.

  • A2-full. Intenta materializar la matriz de similitudes $S = Q^{\top} X$. Antes, calcula su tamaño en bytes S_bytes = m*n*bytes_per_dtype(dtype) y comprueba dos condiciones: (i) que no supere el límite duro A2_MEM_LIMIT_MB, y (ii) que no exceda el 60 % de la RAM libre medida en ese instante (A2_FRAC_FREE). Si alguna falla, se omite A2 (se deja time_s = None pero se reporta el tamaño que habría requerido en mem_MB para documentar por qué se saltó). Si pasa, se mide el tiempo y se informa el pico como el tamaño de $S$.

  • A3-batched. Ajusta el tamaño de lote b con safe_batch, partiendo del presupuesto MEM_BUDGET_MB pero sin rebasar el 30 % de la RAM libre (A3_FRAC_FREE). Luego procesa $Q$ por bloques (maxdot_batched) y reporta como pico batch_bytes = b*n*bytes_per_dtype(dtype). Esta variante es exacta y funciona incluso cuando A2 no cabe, a costa de más pasadas.

Finalmente, la función libera memoria (del Q, X; gc.collect()) y devuelve una lista de tuplas, una por algoritmo, con la forma:

In [70]:
def repeats_for(m, n):
    return 1 if (m*n) >= REPEAT_LARGE_THRESHOLD_PAIRS else 2
def evaluate_case(d, m, n, dtype=np.float32, run_A1=True):
    Q = make_matrix(d, m, dtype=dtype)
    X = make_matrix(d, n, dtype=dtype)
    flop_per_pair = 2*d - 1
    flops_total   = int(flop_per_pair * m * n)
    results = []
    # A0-loops
    if m*n <= A0_LOOPS_MAX_PAIRS:
        t = bench(maxdot_loops, Q, X, repeat=1)   # repeat=1 para no tardar
        results.append(("A0-loops", t, 0, flops_total))
    else:
        results.append(("A0-loops", None, 0, flops_total))
    # A1-naive
    if run_A1 and (m*n <= A1_NAIVE_MAX_PAIRS):
        t = bench(maxdot_naive, Q, X, repeat=repeats_for(m, n))
        results.append(("A1-naive", t, 0, flops_total))
    else:
        results.append(("A1-naive", None, 0, flops_total))
    # A1-adapt
    if run_A1 and (m*n <= A1_ADAPT_MAX_PAIRS):
        t = bench(getmaxdot_many, Q, X, repeat=1)
        results.append(("A1-adapt", t, 0, flops_total))
    else:
        results.append(("A1-adapt", None, 0, flops_total))
    # A2-full
    bytes_per = bytes_per_dtype(dtype)
    S_bytes   = m * n * bytes_per
    avail     = ram_disponible_mb()
    a2_ok = (A2_MEM_LIMIT_MB > 0) and (S_bytes <= A2_MEM_LIMIT_MB * 1e6)
    if avail is not None:
        a2_ok &= (S_bytes <= A2_FRAC_FREE * avail * 1e6)
    if a2_ok:
        t = bench(maxdot_full, Q, X, repeat=repeats_for(m, n))
        results.append(("A2-full", t, S_bytes, flops_total))
    else:
        results.append(("A2-full", None, S_bytes, flops_total))
    # A3-batched
    budget_mb = MEM_BUDGET_MB
    if avail is not None:
        budget_mb = min(MEM_BUDGET_MB, int(A3_FRAC_FREE * avail))
    b_calc = safe_batch(n, dtype=dtype, mem_budget_mb=budget_mb)
    b = min(m, b_calc)
    t = bench(maxdot_batched, Q, X, repeat=repeats_for(m, n), batch=b)
    batch_bytes = b * n * bytes_per
    results.append(("A3-batched", t, batch_bytes, flops_total))
    del Q, X
    gc.collect()
    return results

Verificación de combinaciones y memoria estimada¶

La tabla resume, para cada $(m,n)$ del grid, el tamaño del problema y la memoria que requerirían A2 (matriz completa $S = Q^{\top} X$) y A3.

Conclusiones directas:

  • En los casos pequeños y medianos $(m,n)\in\{10^3,10^4\}$, el tamaño de $S$ está entre 4 MB y 400 MB, por lo que A2 “cabe” (columna A2 cabe = True). Aquí A2 es el candidato más rápido porque hace una sola GEMM.

  • Cuando uno de los tamaños llega a $10^5$, $S$ crece a 4 GB (p. ej., $10^4\times10^5$ o $10^5\times10^4$). Con el límite configurado (A2_MEM_LIMIT_MB = 9000), A2 sigue siendo viable en estos casos.

  • En el caso extremo $(m,n)=(10^5,10^5)$, $S$ subiría a 40 GB, lo que supera el umbral de A2 (A2 cabe = False). Aquí A2 no se ejecuta y se recurre a A3.

  • Para A3, el pico de memoria (pico_A3 MB) se mantiene cercano al presupuesto (MEM_BUDGET_MB \approx 6000\ \text{MB}), porque el tamaño de lote (batch_A3) se ajusta para cumplir ese tope:

    • Con $n=10^3$ o $10^4$, basta 1 pasada (pasadas_A3 = 1), ya que el lote calculado cubre todo $m$.
    • En el caso más grande $(10^5,10^5)$ y $n=10^5$, el lote baja (15,000), por lo que se requieren 7 pasadas. El cálculo es factible con ~6 GB de pico, pero tomará más tiempo que A2.
In [59]:
def bytes_per_dtype(dtype):
  return np.dtype(dtype).itemsize
# Verificación
combos = [(m, n) for m in grid for n in grid]
dfc = pd.DataFrame(combos, columns=['m','n'])
dfc['m·n'] = dfc['m'] * dfc['n']
bytes_per = bytes_per_dtype(dtype)
dfc['≈ mem(S) MB'] = (dfc['m·n'] * bytes_per) / 1e6
dfc['A2 cabe?']    = dfc['≈ mem(S) MB'] <= A2_MEM_LIMIT_MB
batch_calc = (MEM_BUDGET_MB*1_000_000)//(dfc['n']*bytes_per)
dfc['batch_A3']   = batch_calc.clip(lower=1).astype(int)
dfc['pico_A3 MB'] = (dfc['batch_A3']*dfc['n']*bytes_per)/1e6
dfc['pasadas_A3'] = np.ceil(dfc['m']/dfc['batch_A3']).astype(int)
display(dfc.style.hide(axis='index').format({'m':'{:,}','n':'{:,}','m·n':'{:,}',
                                             '≈ mem(S) MB':'{:,.1f}','pico_A3 MB':'{:,.1f}'}))
m n m·n ≈ mem(S) MB A2 cabe? batch_A3 pico_A3 MB pasadas_A3
1,000 1,000 1,000,000 4.0 True 1500000 6,000.0 1
1,000 10,000 10,000,000 40.0 True 150000 6,000.0 1
1,000 100,000 100,000,000 400.0 True 15000 6,000.0 1
10,000 1,000 10,000,000 40.0 True 1500000 6,000.0 1
10,000 10,000 100,000,000 400.0 True 150000 6,000.0 1
10,000 100,000 1,000,000,000 4,000.0 True 15000 6,000.0 1
100,000 1,000 100,000,000 400.0 True 1500000 6,000.0 1
100,000 10,000 1,000,000,000 4,000.0 True 150000 6,000.0 1
100,000 100,000 10,000,000,000 40,000.0 False 15000 6,000.0 7

Ejecución del grid¶

En esta sección recorremos las 9 combinaciones $(m,n)$ del grid y ejecutamos evaluate_case(...) para cada una. La función devuelve, por algoritmo (A0–A3), una tupla con nombre, tiempo (t), memoria pico (mem_peak, en bytes) y flops teóricos. Con esa información armamos una lista de diccionarios rows y luego un DataFrame ordenado y formateado.

  • Para cada algoritmo añadimos: d, m, n, algo, time_s, mem_MB, flops y, en el caso de A3, el tamaño de lote usado (batch_used).
    El lote se reconstruye a partir de la memoria pico estimada: $$\text{batch_used} \approx \frac{\text{mem_peak}}{n \cdot \text{bytes_por_elemento}}.$$

    Esta parte es útil para interpretar cuánto trabajo se hizo por pasada en A3.

  • Los tiempos se redondean a 4 decimales. La memoria se muestra en MB con un decimal. Si un algoritmo no se ejecutó por política/tamaño, time_s queda None y mem_MB muestra, si aplica, el pico teórico (por ejemplo, el tamaño de $S$ en A2 aunque se haya omitido), lo que documenta por qué no se corrió.

  • Ordenamos por m, n y algo para comparar todas las variantes en el mismo problema. El display final usa style para ocultar el índice y aplicar formato numérico con separadores de miles.

In [60]:
# 6) Ejecutar grid y tabla final
rows = []
for m in grid:
    for n in grid:
        res = evaluate_case(d, m, n, dtype=dtype, run_A1=True)
        for name, t, mem_peak, flops in res:
            batch_used = None
            if name == 'A3-batched' and mem_peak is not None:
                batch_used = int(mem_peak // (bytes_per_dtype(dtype)*n))
            rows.append(dict(
                d=d, m=m, n=n, algo=name,
                time_s=None if t is None else round(t, 4),
                mem_MB=None if mem_peak is None else round(mem_peak/1e6, 1),
                flops=flops,
                batch_used=batch_used
            ))

df = pd.DataFrame(rows).sort_values(['m','n','algo']).reset_index(drop=True)
display(df.style.hide(axis='index').format({'m':'{:,}','n':'{:,}','time_s':'{:.4f}','mem_MB':'{:,.1f}'}))
d m n algo time_s mem_MB flops batch_used
8 1,000 1,000 A0-loops 3.6430 0.0 15000000 nan
8 1,000 1,000 A1-adapt 0.0108 0.0 15000000 nan
8 1,000 1,000 A1-naive 0.0103 0.0 15000000 nan
8 1,000 1,000 A2-full 0.0080 4.0 15000000 nan
8 1,000 1,000 A3-batched 0.0080 4.0 15000000 1000.000000
8 1,000 10,000 A0-loops 30.5203 0.0 150000000 nan
8 1,000 10,000 A1-adapt 0.0156 0.0 150000000 nan
8 1,000 10,000 A1-naive 0.0157 0.0 150000000 nan
8 1,000 10,000 A2-full 0.0232 40.0 150000000 nan
8 1,000 10,000 A3-batched 0.0228 40.0 150000000 1000.000000
8 1,000 100,000 A0-loops 309.6573 0.0 1500000000 nan
8 1,000 100,000 A1-adapt 0.2131 0.0 1500000000 nan
8 1,000 100,000 A1-naive 0.2232 0.0 1500000000 nan
8 1,000 100,000 A2-full 0.2255 400.0 1500000000 nan
8 1,000 100,000 A3-batched 0.2392 400.0 1500000000 1000.000000
8 10,000 1,000 A0-loops 31.2270 0.0 150000000 nan
8 10,000 1,000 A1-adapt 0.0659 0.0 150000000 nan
8 10,000 1,000 A1-naive 0.0656 0.0 150000000 nan
8 10,000 1,000 A2-full 0.0313 40.0 150000000 nan
8 10,000 1,000 A3-batched 0.0273 40.0 150000000 10000.000000
8 10,000 10,000 A0-loops 303.9815 0.0 1500000000 nan
8 10,000 10,000 A1-adapt 0.1531 0.0 1500000000 nan
8 10,000 10,000 A1-naive 0.1593 0.0 1500000000 nan
8 10,000 10,000 A2-full 0.2378 400.0 1500000000 nan
8 10,000 10,000 A3-batched 0.2480 400.0 1500000000 10000.000000
8 10,000 100,000 A0-loops nan 0.0 15000000000 nan
8 10,000 100,000 A1-adapt nan 0.0 15000000000 nan
8 10,000 100,000 A1-naive nan 0.0 15000000000 nan
8 10,000 100,000 A2-full 2.2268 4,000.0 15000000000 nan
8 10,000 100,000 A3-batched 2.8201 3,616.0 15000000000 9040.000000
8 100,000 1,000 A0-loops 305.4651 0.0 1500000000 nan
8 100,000 1,000 A1-adapt 0.7604 0.0 1500000000 nan
8 100,000 1,000 A1-naive 0.6800 0.0 1500000000 nan
8 100,000 1,000 A2-full 0.2496 400.0 1500000000 nan
8 100,000 1,000 A3-batched 0.2511 400.0 1500000000 100000.000000
8 100,000 10,000 A0-loops nan 0.0 15000000000 nan
8 100,000 10,000 A1-adapt nan 0.0 15000000000 nan
8 100,000 10,000 A1-naive nan 0.0 15000000000 nan
8 100,000 10,000 A2-full 2.7096 4,000.0 15000000000 nan
8 100,000 10,000 A3-batched 2.2759 3,599.0 15000000000 89975.000000
8 100,000 100,000 A0-loops nan 0.0 150000000000 nan
8 100,000 100,000 A1-adapt nan 0.0 150000000000 nan
8 100,000 100,000 A1-naive nan 0.0 150000000000 nan
8 100,000 100,000 A2-full nan 40,000.0 150000000000 nan
8 100,000 100,000 A3-batched 23.3785 3,600.0 150000000000 9000.000000 
CSV guardado en: /content/resultados_grid.csv

Interpretación de la tabla¶

Es importante mencionar que cuando time_s está vacío y/o batch_used = NaN, el algoritmo NO se ejecutó (se omitió por límites de memoria/recursos o por políticas). En esas filas, los demás campos mem_MB y time_s no serian los correctos porque no se ejecutó.

n = 1 000¶

  • (m = 1 000) time_s ≈ 0.008, mem ≈ 4 MB, batch_used = 1 000 → 1 pasada.
  • (m = 10 000) time_s ≈ 0.0273, mem ≈ 40 MB, batch_used = 10 000 → 1 pasada.
  • (m = 100 000) time_s ≈ 0.2511, mem ≈ 400 MB, batch_used = 100 000 → 1 pasada.
    Lectura: con una sola pasada, el tiempo crece al aumentar m.

n = 10 000¶

  • (m = 1 000) time_s ≈ 0.0228, mem ≈ 40 MB, batch_used = 1 000 → 1 pasada.
  • (m = 10 000) time_s ≈ 0.2480, mem ≈ 400 MB, batch_used = 10 000 → 1 pasada.
  • (m = 100 000) time_s ≈ 2.2759, mem ≈ 3 599 MB, batch_used ≈ 89 975 → 2 pasadas ($\lceil 100{,}000/89{,}975 \rceil = 2$).
    Lectura: al subir n, aumenta el costo por pasada; cuando batch_used < m aparecen más pasadas y el tiempo sube casi en proporción.

n = 100 000¶

  • (m = 1 000) time_s ≈ 0.2392, mem ≈ 400 MB, batch_used = 1 000 → 1 pasada.
  • (m = 10 000) time_s ≈ 2.8201, mem ≈ 3 616 MB, batch_used ≈ 9 040 → 2 pasadas ($\lceil 10{,}000/9{,}040 \rceil = 2$).
  • (m = 100 000) time_s ≈ 23.3785, mem ≈ 3 600 MB, batch_used ≈ 9 000 → 12 pasadas ($\lceil 100{,}000/9{,}000 \rceil = 12$).

Conclusión¶

En esta corrida, el único algoritmo que pudimos ejecutar de forma consistente fue A3-batched. El resto de variantes (A0, A1-naive/A1-adapt y A2-full) no se ejecutaron en varios casos por limitaciones técnicas de memoria/tiempo y por las políticas establecidas para evitar corridas interminables. Por ello, no se alcanzó la comparación esperada entre algoritmos: los únicos resultados válidos para análisis son las filas donde aparece batch_used (A3).

Aun así, los resultados de A3 permiten extraer patrones claros. Cuando $n$ es pequeño o mediano y el lote calculado cubre todo $m$ (es decir, 1 pasada), los tiempos son bajos (del orden de milisegundos a décimas de segundo). A medida que crece $n$, para respetar el presupuesto de memoria el batch_used disminuye y el número de pasadas $\lceil m/b\rceil$ aumenta, lo que eleva los tiempos a escala de segundos (con 2 pasadas) o incluso decenas de segundos (con $\sim 12$ pasadas), como ocurre en el caso $(m,n)=(10^5,10^5)$. En otras palabras, el cuello de botella surge cuando $n$ es grande: el pico de memoria se mantiene bajo control, pero se paga con más pasadas y mayor tiempo total.

En síntesis, los datos disponibles muestran que A3-batched es una estrategia exacta y operable bajo límites de memoria estrictos, pero su tiempo depende del número de pasadas impuesto por el presupuesto. Para alcanzar la comparación integral entre A0–A3 que se había planeado, se requeriría ejecutar también A2 (y eventualmente A1) en más combinaciones, lo cual no fue viable con los recursos actuales; por ello, las conclusiones cuantitativas comparativas deben quedar acotadas a los casos en que sí hubo ejecución real.

Bibliografía¶

  • Dongarra, J., du Croz, J., Duff, I., & Hammarling, S. (1990). An extended set of FORTRAN basic linear algebra subprograms. ACM Transactions on Mathematical Software, 16(1), 1–17.

  • Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations (4.ª ed.). Johns Hopkins University Press.

  • Goto, K., & Van de Geijn, R. A. (2008). Anatomy of high-performance matrix multiplication. ACM Transactions on Mathematical Software, 34(3), 12:1–12:25.

  • Harris, C. R., Millman, K. J., van der Walt, S. J., et al. (2020). Array programming with NumPy. Nature, 585, 357–362.

  • Hunter, J. D. (2007). Matplotlib: A 2D graphics environment. Computing in Science & Engineering, 9(3), 90–95.

  • Virtanen, P., Gommers, R., Oliphant, T. E., et al. (2020). SciPy 1.0: Fundamental algorithms for scientific computing in Python. Nature Methods, 17, 261–272.

  • Vitter, J. S. (2008). Algorithms and data structures for external memory. Foundations and Trends in Theoretical Computer Science, 2(4), 305–474.