Introducción

La programación paralela y el diseño de programas paralelos eficientes están bien establecidos en High Performance Computer (HPC) durante muchos años. En las últimas décadas, la investigación en tecnologías de HW y SW en paralelo para HPC ha tenido grandes avances (e.g. NVIDIA CUDA). Las aplicaciones más comunes son simulaciones de condiciones ambientales para predicción del tiempo en función de complejas funciones matemáticas, resolución de ecuaciones diferenciales en astronomía, secuenciamiento genómico, inteligencia artificial, simulación de choques en la industria automotriz.

¿Por qué programación en paralelo? Limitaciones de un solo procesador:

• Rendimiento
• Memoria Problemas que se solucionan:
• Problemas con mayor cantidad de datos.
• Problemas que deben solucionarse en tiempos altamente restrictivos

Arquitectura de procesadores - Tecnología

1. Paralelismo a nivel de bit

   • Realizar cálculos con varios bits en simultáneo.
   • Máximo valor para arquitecturas actuales → 64 bits.

2. Paralelismo por pipeline

   • De 2 a 26 etapas, dependiente de la arquitectura (RISC o CISC).
   • Superpipelining → pipelines más profundos y rápidos.
   • Problemas:
     • Dependencias de datos
     • Riesgos estructurales
     • Riesgos de control (saltos)

3. Paralelismo por múltiples unidades funcionales

   • Diferentes unidades trabajando en paralelo: ALU, FPU, unidades de salto, load/store.
   • Arquitecturas superescalares y VLIW (Very Long Instruction Word).
   • Restricciones: ILP disponible y dependencias de datos.
   • Emisión simple vs. emisión múltiple (1, 2, 3 o más instrucciones por ciclo).

4. Paralelismo por procesos o Thread Level Parallelism (TLP)

   • Ejecución simultánea de múltiples hilos o procesos independientes.
   • Hilos comparten memoria; procesos no.
   • Aprovecha múltiples núcleos y hardware multithreading (SMT / Hyperthreading).
   • Ventajas: tolera latencias largas.
   • Desventajas: sincronización, contención y overhead de comunicación.

5. Paralelismo por múltiples núcleos (CMP: Chip Multiprocessor)

   • Varios núcleos completos en un mismo chip.
   • Cada núcleo con su propio pipeline y unidades funcionales.
   • Permite verdadero paralelismo entre hilos.
   • Caches compartidas → coherencia con MESI/MOESI.
   • Escala bien cuando las tareas son independientes.

Consideraciones

Las formas de paralelismo previamente mencionadas asumen un control de flujo single sequential por el compilador. Esto determina el orden de ejecución.

• Desde el punto de vista del programador tiene la ventaja de programación secuencial y ejecución de instrucciones en paralelo.
• Límites alcanzados - Ley de Moore → incrementar el tamaño de la memoria caché (más transistores en el integrado de Si)
• ¿Problema? Penalización por mayores tiempos de acceso.

Métricas para evaluar el nivel de paralelismo

Ley de Amdalh

Ley de Gustafson (Gustafson-Barsis)

• Nace como respuesta a la Ley de Amdahl.
• Su definición no está basada en el tiempo de ejecución sino en la cantidad de trabajo que se puede ahorrar ante el procesamiento paralelo.
• Esta ley postula que a medida que aumentamos el tamaño total de los problemas a resolver, se aprovecha de manera efectiva la computación paralela.

Scaled SUP = (Tiempo que toma el trabajo a realizar) / (Tiempo que toma el trabajo usando N procesadores)

Scaled SUP = (s + Np) / (s+p) = (s + Np) = Ns + N(1-s) + Np = N + (1-N)s

Ley de Karp-Flat

• Es una métrica alternativa para medir el rendimiento de un algoritmo paralelo propuesto por Alan H. Karp y Horace P. Flatt
• Se introduce el concepto de “fracción serial determinada”, el cual es una medida de la fracción de la ejecución de un programa paralelo que es inherentemente secuencial. Por tanto, no se calcula propiamente un SUP pero sí ayuda a entender la eficiencia del paralelismo en un programa.
• La diferencia con la ley de Amdahl es que Karp-Flatt reconoce que la fracción paralelizable no está libre de ser afectada por carga de trabajo y arquitectura del sistema.

Ts: Tiempo sin mejora

Tm: Tiempo con mejora

SUP = Ts / Tm

Idealmente: SUP = N

En la práctica, sea f' la fracción serial: Tm = (f')(Ts) + (1-f') Ts / N

Por Amdahl: SUP = 1 / (f' + (1-f’) / N)

Despejando: f’ = (1 / SUP - 1 / N) / (1 - 1 / N)

A diferencia de las leyes anteriores, esta ley busca predecir la fracción serial efectiva, la cual incluye overhead, sincronización, comunicación, entre otros.

Multiprocessing

multiprocessing es un módulo de Python que permite ejecutar varias funciones al mismo tiempo usando procesos independientes.
Cada proceso tiene su propia memoria y puede ejecutarse en un núcleo distinto del CPU, logrando paralelismo real.

Cuando usamos multiprocessing:

• El programa principal crea procesos hijos.
• Cada proceso hijo ejecuta una función específica.
• Los procesos pueden ejecutarse en paralelo, aprovechando varios núcleos.
• Cada proceso tiene su propio espacio de memoria, separado del proceso padre.
• Para coordinar la ejecución, se usa:
  • start() → iniciar el proceso
  • join() → esperar a que termine

¿Por qué usar multiprocessing?

Se utiliza cuando necesitamos acelerar tareas CPU-bound, como:

• Cálculos matemáticos pesados
• Procesamiento de imágenes o señales
• Simulaciones numéricas
• Algoritmos que consumen mucho CPU

El módulo permite dividir el trabajo en partes y ejecutarlas en paralelo, reduciendo significativamente el tiempo de ejecución cuando hay varios núcleos disponibles.

Ejemplo

import multiprocessing as mp
import time
import math

# Trabajo pesado (CPU-bound)
def heavy_compute(n):
    s = 0.0
    for i in range(n):
        s += math.sqrt((i * i) % 1000)
    return s

def sin_multiprocessing(num_tareas, trabajo_por_tarea):
    t0 = time.perf_counter()
    resultados = []
    for _ in range(num_tareas):
        resultados.append(heavy_compute(trabajo_por_tarea))
    t1 = time.perf_counter()
    return t1 - t0, resultados

def con_multiprocessing(num_tareas, trabajo_por_tarea):
    t0 = time.perf_counter()
    with mp.Pool(processes=mp.cpu_count()) as pool:
        resultados = pool.map(heavy_compute, [trabajo_por_tarea] * num_tareas)
    t1 = time.perf_counter()
    return t1 - t0, resultados

if __name__ == "__main__":

    NUM_TAREAS = 8
    TRABAJO_POR_TAREA = int(1e6) 

    print(f"Núcleos disponibles: {mp.cpu_count()}")
    print(f"Número de tareas   : {NUM_TAREAS}")
    print(f"Trabajo por tarea  : {TRABAJO_POR_TAREA:,} iteraciones\n")

    # Secuencial
    t_seq, res_seq = sin_multiprocessing(NUM_TAREAS, TRABAJO_POR_TAREA)
    print(sum(res_seq))
    print(f"Tiempo sin multiprocessing : {t_seq:.10f} s")

    # Paralela
    t_par, res_par = con_multiprocessing(NUM_TAREAS, TRABAJO_POR_TAREA)
    print(sum(res_par))
    print(f"Tiempo con multiprocessing : {t_par:.10f} s")

    # Speedup
    print(f"\nSpeedup aproximado: {t_seq / t_par:.2f}")

Ejemplo Matriz-Vector

import time
import numpy as np
from multiprocessing import Pool, cpu_count
from itertools import repeat

# Matriz - Vector
def matvec_python(mat, vec, out):
    for j in range(len(vec)):
        acc = 0
        for i in range(len(vec)):
            acc += mat[j, i] * vec[i]
        out[j] = acc

# vector - vector - para ser usado por multiprocessing
def dot_worker(row, vec):
    s = 0
    for i in range(len(vec)):
        s += row[i] * vec[i]
    return s

# Versión paralela con multiprocessing
def matvec_parallel(mat, vec, num_procs):
    with Pool(processes=num_procs) as p:
        args = zip(mat, repeat(vec))
        result = p.starmap(dot_worker, args)
    return result


if __name__ == "__main__":
    M = 2048
    N = 2048

    # Matriz y vector 
    A = np.random.randint(9, size=(M, N))
    x = np.random.randint(9, size=(N,))
    out_python = np.zeros_like(x)

    # 1. NumPy (baseline)
    t0 = time.perf_counter()
    y_numpy = A.dot(x)
    t1 = time.perf_counter()

    # 2. Secuencial Python
    t2 = time.perf_counter()
    matvec_python(A, x, out_python)
    t3 = time.perf_counter()

    # 3. Paralelo Python (multiprocessing)
    NUM_PROCS = cpu_count()       # usa todos los cores disponibles
    t4 = time.perf_counter()
    y_parallel = matvec_parallel(A, x, NUM_PROCS)
    t5 = time.perf_counter()

    # -------------------------
    # Resultados
    # -------------------------
    print("\n=== Tiempos (en segundos) ===")
    print(f"NumPy dot            : {t1 - t0:.4f} s")
    print(f"Secuencial Python    : {t3 - t2:.4f} s")
    print(f"Paralelo ({NUM_PROCS} procesos): {t5 - t4:.4f} s")

    # Validación
    diff_seq = np.max(np.abs(out_python - y_numpy))
    diff_par = np.max(np.abs(np.array(y_parallel) - y_numpy))

    print("\n=== Validación numérica ===")
    print("Max diferencia secuencial :", diff_seq)
    print("Max diferencia paralelo   :", diff_par)