El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Paral·lelització d'Algorismes

Següent ►
►

La paral·lelització d'algorismes és una tècnica que permet executar múltiples parts d'un algorisme simultàniament, aprofitant els recursos de maquinari disponibles, com ara processadors multicore o sistemes distribuïts. Aquesta tècnica pot millorar significativament el rendiment i l'eficiència dels algorismes, especialment en tasques que requereixen un alt poder de càlcul.

Conceptes Clau

  1. Paral·lelisme de Dades vs. Paral·lelisme de Tasques:

    • Paral·lelisme de Dades: Consisteix a dividir les dades en parts més petites que es poden processar simultàniament.
    • Paral·lelisme de Tasques: Consisteix a dividir l'algorisme en tasques independents que es poden executar en paral·lel.

  2. Models de Programació Paral·lela:

    • Memòria Compartida: Tots els processadors accedeixen a una memòria comuna.
    • Memòria Distribuïda: Cada processador té la seva pròpia memòria local i es comuniquen entre ells mitjançant missatges.

  3. Sincronització i Comunicació:

    • Locks i Semàfors: Mecanismes per controlar l'accés concurrent a recursos compartits.
    • Barreres: Punts de sincronització on tots els fils han d'arribar abans de continuar.

  4. Granularitat del Paral·lelisme:

    • Granularitat Fina: Moltes tasques petites que es poden executar en paral·lel.
    • Granularitat Gruixuda: Poques tasques grans que es poden executar en paral·lel.

Exemples Pràctics

Exemple 1: Suma de Vectors

Un exemple senzill de paral·lelització és la suma de dos vectors. Suposem que tenim dos vectors A i B de longitud n, i volem calcular el vector C tal que C[i] = A[i] + B[i].

Codi Seqüencial

def suma_vectors(A, B):
    n = len(A)
    C = [0] * n
    for i in range(n):
        C[i] = A[i] + B[i]
    return C

Codi Paral·lel (usant multiprocessing en Python)

import multiprocessing

def suma_parcial(A, B, C, start, end):
    for i in range(start, end):
        C[i] = A[i] + B[i]

def suma_vectors_paralel(A, B):
    n = len(A)
    C = multiprocessing.Array('i', n)
    num_processos = multiprocessing.cpu_count()
    processos = []
    chunk_size = n // num_processos

    for i in range(num_processos):
        start = i * chunk_size
        end = n if i == num_processos - 1 else (i + 1) * chunk_size
        p = multiprocessing.Process(target=suma_parcial, args=(A, B, C, start, end))
        processos.append(p)
        p.start()

    for p in processos:
        p.join()

    return list(C)

Exemple 2: Ordenació Paral·lela (Merge Sort)

L'algorisme Merge Sort es pot paral·lelitzar dividint el problema en subproblemes més petits que es poden resoldre en paral·lel.

Codi Seqüencial

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

Codi Paral·lel (usant multiprocessing en Python)

import multiprocessing

def merge_sort_parallel(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    with multiprocessing.Pool(processes=2) as pool:
        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

Exercicis Pràctics

Exercici 1: Multiplicació de Matrius

Implementa la multiplicació de dues matrius de manera paral·lela. Pots utilitzar la biblioteca multiprocessing de Python.

Exercici 2: Cerca Paral·lela

Implementa una cerca binària paral·lela en una llista ordenada. Divideix la llista en subllistes i realitza la cerca en paral·lel.

Errors Comuns i Consells

  1. Condicions de Carrera: Assegura't de sincronitzar correctament l'accés a recursos compartits per evitar condicions de carrera.
  2. Sobrecàrrega de Comunicació: La comunicació entre processos pot introduir una sobrecàrrega significativa. Assegura't que la granularitat del paral·lelisme sigui adequada.
  3. Equilibri de Càrrega: Distribueix les tasques de manera equitativa entre els processos per evitar que alguns processos estiguin inactius mentre altres estan sobrecarregats.

Conclusió

La paral·lelització d'algorismes és una tècnica poderosa per millorar el rendiment dels algorismes. Comprendre els conceptes clau i aplicar-los correctament pot portar a una millora significativa en l'eficiència del codi. Amb la pràctica i l'experimentació, podràs identificar les millors estratègies per paral·lelitzar els teus algorismes i optimitzar el rendiment del teu codi.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats