Exemplo 2: Buscando o máximo em paralelo

A mesma ideia de dividir um array em fatias, dar cada fatia para uma thread e juntar os resultados no final funciona para qualquer operação que possa ser decomposta em partes independentes. Aqui, aplicamos ela para encontrar o valor máximo.

#include <stdio.h>
#include <pthread.h>
#include <limits.h>

#define N_THREADS 4
#define N_ELEMS   16

typedef struct {
    const int *data;
    size_t     len;
} Slice;

void *partial_max(void *arg) {
    Slice *s = arg;
    int max = INT_MIN;
    for (size_t i = 0; i < s->len; i++) {
        if (s->data[i] > max)
            max = s->data[i];
    }
    return (void *)(long)max;
}

int main(void) {
    int data[] = {3, 41, 15, 92, 65, 35, 89, 79,
                  32, 38, 46, 26, 53, 58, 97, 23};

    size_t chunk = N_ELEMS / N_THREADS;
    pthread_t tids[N_THREADS];
    Slice     slices[N_THREADS];

    for (int t = 0; t < N_THREADS; t++) {
        slices[t].data = data + t * chunk;
        slices[t].len  = (t == N_THREADS - 1)
                       ? N_ELEMS - t * chunk
                       : chunk;
        pthread_create(&tids[t], NULL, partial_max, &slices[t]);
    }

    int global_max = INT_MIN;
    for (int t = 0; t < N_THREADS; t++) {
        void *res;
        pthread_join(tids[t], &res);
        int local_max = (int)(long)res;
        if (local_max > global_max)
            global_max = local_max;
    }

    printf("max = %d\n", global_max);
}

Código 5-3: Buscando o máximo de um array com 4 threads.

A estrutura é a mesma do exemplo anterior: Slice, divisão em fatias, coleta via pthread_join. O que muda é a operação: cada thread calcula o máximo local da sua fatia, e a thread principal compara os 4 máximos locais para encontrar o global.

Tanto a soma quanto o máximo são operações associativas: não importa como dividimos os elementos entre as threads, o resultado final é o mesmo¹.

Esse padrão é um caso particular de Map-Reduce ou fan-out/fan-in: a fase “map” aplica uma função a cada fatia (soma parcial, máximo parcial, etc.), e a fase “reduce” combina os resultados num único valor. ↩

Keyboard shortcuts

Programação Paralela e Concorrente

Exemplo 2: Buscando o máximo em paralelo