Algoritmos paralelos y su complejidad

6.1 Algoritmos paralelos.

Los algoritmos paralelos están diseñados para ejecutarse en sistemas multiprocesador o multihilo con el objetivo de acelerar los cálculos. Dividen la tarea en subtareas independientes que se ejecutan simultáneamente. El análisis de la complejidad de los algoritmos paralelos requiere tener en cuenta tanto la complejidad temporal como la espacial, así como factores como la aceleración, la eficiencia y la escalabilidad.

Conceptos básicos de los algoritmos paralelos

• Paralelismo: División de una tarea en varias subtareas que pueden ejecutarse simultáneamente.
• Aceleración (Speedup): Relación entre el tiempo de ejecución del algoritmo secuencial y el tiempo de ejecución del algoritmo paralelo.
• Eficiencia (Efficiency): Relación entre la aceleración y la cantidad de procesadores.
• Escalabilidad (Scalability): Capacidad del algoritmo paralelo para utilizar eficazmente un número creciente de procesadores.

Ventajas de los algoritmos paralelos:

• Aceleración de la ejecución: Realizar tareas más rápido a través de la paralelización del trabajo.
• Uso eficiente de recursos: Optimización del uso de procesadores y núcleos.
• Resolución de tareas grandes: Capacidad para procesar grandes volúmenes de datos y cálculos complejos que son imposibles o muy lentos en un solo procesador.

Complejidad temporal de los algoritmos paralelos

La complejidad temporal de los algoritmos paralelos se mide teniendo en cuenta el tiempo dedicado a ejecutar todas las subtareas paralelas y la sincronización entre ellas. Incluye:

• Complejidad temporal teórica: Tiempo ideal de ejecución en un número infinito de procesadores.
• Complejidad temporal real: Tiempo de ejecución teniendo en cuenta las limitaciones en el número de procesadores y los gastos generales de sincronización.

Complejidad espacial de los algoritmos paralelos

La complejidad espacial de los algoritmos paralelos considera el volumen de memoria necesario para almacenar datos y el contexto de cada proceso paralelo. También es importante tener en cuenta los gastos generales de comunicación entre los procesadores.

6.2 Ejemplo de un algoritmo paralelo

Ordenación por mezcla paralela (Parallel Merge Sort):

Divide el arreglo en subarreglos, los ordena en paralelo y luego los fusiona.

Complejidad temporal: O(n*log(n)/p), donde n es el tamaño del arreglo, p es la cantidad de procesadores.

from multiprocessing import Pool

def merge_sort_parallel(arr, num_processes=None):
    if len(arr) <= 1:
        return arr
    if num_processes is None:
        num_processes = Pool()._processes
    with Pool(processes=num_processes) as pool:
        size = len(arr) // 2
        left, right = arr[:size], arr[size:]
        left, right = pool.map(merge_sort_parallel, [left, right])
        return merge(left, right)
            
def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result
            
# Ejemplo de uso
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = merge_sort_parallel(arr)
print(sorted_arr)
            

Pero lo que nos interesará no es el algoritmo en sí, sino el análisis de su «eficiencia».

6.3 Análisis de algoritmos paralelos

Conceptos básicos:

1. Análisis de aceleración (Speedup):
   • Relación entre el tiempo de ejecución del algoritmo secuencial y el tiempo de ejecución del algoritmo paralelo.
   • Speedup = T_seq / T_par, donde T_seq es el tiempo de ejecución del algoritmo secuencial, T_par es el tiempo de ejecución del algoritmo paralelo.
2. Eficiencia (Efficiency):
   • Evaluación de la eficiencia en el uso de procesadores.
   • Efficiency = Speedup / P, donde P es la cantidad de procesadores.
3. La ley de Amdahl (Amdahl's Law):
   • Determina la aceleración máxima que se puede lograr al paralelizar una tarea.
   • Speedup_max = 1 / (S + (1 - S) / P), donde S es la fracción de la parte secuencial de la tarea, P es la cantidad de procesadores.
4. La ley de Gustafson (Gustafson's Law):
   • Determina la aceleración teniendo en cuenta el cambio en el tamaño de la tarea al aumentar la cantidad de procesadores.
   • Speedup = P - α * (P - 1), donde P es la cantidad de procesadores, α es la fracción de la parte secuencial de la tarea.

6.4 Ejemplos de algoritmos paralelos y su complejidad

Ejemplo 1: Ordenación por mezcla paralela (Parallel Merge Sort)

Descripción: La ordenación por mezcla paralela divide el arreglo en subarreglos, ordena cada subarreglo en paralelo y luego fusiona los subarreglos ordenados.

Análisis de complejidad:

• Complejidad temporal: O((n log n) / P), donde P es la cantidad de procesadores.
• Complejidad espacial: O(n) para almacenar datos intermedios.

Ejemplo 2: Búsqueda paralela en un arreglo (Parallel Search)

Descripción: La tarea de buscar un elemento en un arreglo se divide en varias subtareas, cada una de las cuales se ejecuta en paralelo en un procesador separado.

Análisis de complejidad:

• Complejidad temporal: O(n / P), donde P es la cantidad de procesadores.
• Complejidad espacial: O(1), si se utiliza el mismo arreglo.

Ejemplo 3: Multiplicación de matrices paralela (Parallel Matrix Multiplication)

Descripción: Las matrices se dividen en bloques y cada par de bloques se multiplica en paralelo en diferentes procesadores.

Análisis de complejidad:

• Complejidad temporal: O(n^3 / P), donde P es la cantidad de procesadores.
• Complejidad espacial: O(n^2) para almacenar los resultados intermedios.

6.5 Implementación de algoritmos paralelos

Herramientas y bibliotecas:

1. OpenMP:
   • Biblioteca para C, C++ y Fortran que proporciona herramientas para desarrollar aplicaciones multihilo.
2. MPI (Message Passing Interface):
   • Estándar para programación paralela en sistemas distribuidos, que soporta el intercambio de mensajes entre procesos.
3. CUDA:
   • Plataforma y API de NVIDIA para desarrollar programas paralelos que utilizan procesadores gráficos (GPU).
4. Threading y multiprocessing en Python:
   • Módulos para crear programas multihilo y multiproceso en Python.

Los algoritmos paralelos permiten acelerar significativamente los cálculos mediante la paralelización de tareas en varios procesadores o núcleos. El análisis de la complejidad de los algoritmos paralelos incluye la evaluación de la aceleración, la eficiencia y el uso de las leyes de Amdahl y Gustafson para comprender la aceleración máxima alcanzable mediante la paralelización.

Los algoritmos paralelos se aplican en diversas áreas, desde la ordenación y búsqueda hasta cálculos matemáticos complejos, y requieren el uso de herramientas especializadas y bibliotecas para su implementación.

¡Importante! No necesitas entusiasmarte demasiado con los algoritmos paralelos. En primer lugar, debido a la ley de Amdahl, no son tan efectivos como parece. En segundo lugar, hoy en día, los servidores con 30 procesadores manejan 3000 solicitudes por minuto, y aún tenemos n tareas para 1 procesador, no 1 tarea para n procesadores.

En tercer lugar, las tareas reales que necesitan acelerarse mediante multiprocesamiento han migrado a los GPU (tarjetas gráficas), y su código se escribe en lenguajes de bajo nivel como C.