Algoritmos Paralelos e sua Complexidade

6.1 Algoritmos Paralelos.

Algoritmos paralelos são projetados para execução em sistemas multiprocessadores ou multithreaded com o objetivo de acelerar o processamento. Eles dividem a tarefa em subtarefas independentes, que são executadas simultaneamente. A análise da complexidade de algoritmos paralelos requer consideração tanto da complexidade de tempo quanto da complexidade de espaço, além de fatores como aceleração, eficiência e escalabilidade.

Conceitos básicos de algoritmos paralelos

• Paralelismo: Divisão da tarefa em várias subtarefas, que podem ser executadas simultaneamente.
• Aceleração (Speedup): Relação entre o tempo de execução do algoritmo sequencial e o tempo de execução do algoritmo paralelo.
• Eficiência (Efficiency): Relação entre a aceleração e o número de processadores.
• Escalabilidade (Scalability): Capacidade do algoritmo paralelo de utilizar eficazmente um número crescente de processadores.

Vantagens dos algoritmos paralelos:

• Aceleração do processamento: Realização de tarefas mais rapidamente através da paralelização do trabalho.
• Uso eficiente dos recursos: Otimização do uso de processadores e núcleos.
• Resolução de grandes tarefas: Capacidade de processar grandes volumes de dados e cálculos complexos, que são impossíveis ou muito lentos em um único processador.

Complexidade de tempo dos algoritmos paralelos

A complexidade de tempo dos algoritmos paralelos é medida considerando o tempo gasto na execução de todas as subtarefas paralelas e na sincronização entre elas. Ela inclui:

• Complexidade de tempo teórica: Tempo ideal de execução em um número infinito de processadores.
• Complexidade de tempo real: Tempo de execução considerando as limitações do número de processadores e os custos de sincronização.

Complexidade de espaço dos algoritmos paralelos

A complexidade de espaço dos algoritmos paralelos considera o volume de memória necessário para armazenar os dados e o contexto de cada processo paralelo. É importante também considerar os custos de comunicação entre os processadores.

6.2 Exemplo de algoritmo paralelo

Ordenação por mistura paralela (Parallel Merge Sort):

Divide o array em subarrays, os ordena paralelamente e depois os mescla.

Complexidade de tempo: O(n*log(n)/p), onde n — tamanho do array, p — número de processadores.

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
            
# Exemplo de uso
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = merge_sort_parallel(arr)
print(sorted_arr)
            

Mas o que nos interessa não é o próprio algoritmo, mas a análise de sua "eficiência".

6.3 Análise de algoritmos paralelos

Conceitos básicos:

1. Análise de aceleração (Speedup):
   • Relação entre o tempo de execução do algoritmo sequencial e o tempo de execução do algoritmo paralelo.
   • Speedup = T_seq / T_par, onde T_seq — tempo de execução do algoritmo sequencial, T_par — tempo de execução do algoritmo paralelo.
2. Eficiência (Efficiency):
   • Avaliação da eficácia do uso de processadores.
   • Efficiency = Speedup / P, onde P — número de processadores.
3. Lei de Amdahl (Amdahl's Law):
   • Define a aceleração máxima que pode ser alcançada ao paralelizar uma tarefa.
   • Speedup_max = 1 / (S + (1 - S) / P), onde S — parte sequencial da tarefa, P — número de processadores.
4. Lei de Gustafson (Gustafson's Law):
   • Define a aceleração considerando a alteração do tamanho da tarefa ao aumentar o número de processadores.
   • Speedup = P - α * (P - 1), onde P — número de processadores, α — parte sequencial da tarefa.

6.4 Exemplos de algoritmos paralelos e sua complexidade

Exemplo 1: Ordenação por mistura paralela (Parallel Merge Sort)

Descrição: A ordenação por mistura paralela divide o array em subarrays, ordena cada subarray paralelamente e depois mescla os subarrays ordenados.

Análise de complexidade:

• Complexidade de tempo: O((n log n) / P), onde P — número de processadores.
• Complexidade de espaço: O(n) para armazenar dados intermediários.

Exemplo 2: Busca paralela em array (Parallel Search)

Descrição: A tarefa de buscar um elemento no array é dividida em várias subtarefas, cada uma das quais é executada paralelamente em um processador separado.

Análise de complexidade:

• Complexidade de tempo: O(n / P), onde P — número de processadores.
• Complexidade de espaço: O(1), se o mesmo array for usado.

Exemplo 3: Multiplicação de matrizes paralela (Parallel Matrix Multiplication)

Descrição: As matrizes são divididas em blocos, e cada par de blocos é multiplicado paralelamente em diferentes processadores.

Análise de complexidade:

• Complexidade de tempo: O(n^3 / P), onde P — número de processadores.
• Complexidade de espaço: O(n^2) para armazenar resultados intermediários.

6.5 Implementação de algoritmos paralelos

Ferramentas e bibliotecas:

1. OpenMP:
   • Biblioteca para C, C++ e Fortran, que oferece recursos para desenvolvimento de aplicações multithreaded.
2. MPI (Message Passing Interface):
   • Padrão para programação paralela em sistemas distribuídos, suportando a troca de mensagens entre processos.
3. CUDA:
   • Plataforma e API da NVIDIA para desenvolvimento de programas paralelos, utilizando processadores gráficos (GPU).
4. Threading e multiprocessing em Python:
   • Módulos para criar programas multithreaded e multiprocessos em Python.

Algoritmos paralelos permitem acelerar significativamente os cálculos através da paralelização de tarefas em vários processadores ou núcleos. A análise da complexidade dos algoritmos paralelos inclui a avaliação da aceleração, eficiência e uso das leis de Amdahl e Gustafson para entender a aceleração máxima alcançável através da paralelização.

Algoritmos paralelos têm aplicação em diversas áreas, desde ordenação e busca até cálculos matemáticos complexos, e requerem o uso de ferramentas especializadas e bibliotecas para sua implementação.

Importante! Não precisa se empolgar demais com algoritmos paralelos. Primeiro, devido à lei de Amdahl, eles não são tão eficazes como parecem. Segundo, hoje em dia servidores com 30 processadores processam 3000 requisições por minuto, e ainda assim temos n tarefas para 1 processador, não 1 tarefa para n processadores.

Em terceiro lugar, tarefas reais que precisam ser aceleradas por multiprocessamento já migraram para GPUs (placas de vídeo), e o código delas é escrito em linguagens de baixo nível como C.