# Introdução à computação paralela

Speedup, eficiência e tempo de execução, com um cálculo completo e a sua interpretação.

Página: https://resumos.rgo.pt/cadeiras/cpd/computacao-paralela-introducao/

Um programa sequencial corre as instruções uma a uma. Um programa paralelo divide o trabalho por vários núcleos que avançam ao mesmo tempo. Esta página fixa o vocabulário mínimo da cadeira e as três medidas com que vais julgar qualquer paralelização.

## O vocabulário base

Um **processo** é um programa em execução com o seu espaço de memória. Uma **thread** é uma linha de execução dentro de um processo, que partilha a memória com as outras threads do mesmo processo. Um **núcleo** (_core_) é a unidade física do processador que executa instruções. Na parte paralela da cadeira trabalhas quase sempre com threads do mesmo processo em memória partilhada, tipicamente com OpenMP.

Dizemos que um trecho é **paralelizável** quando pode ser dividido em partes independentes. Somar os elementos de um vetor é paralelizável, porque cada núcleo soma uma fatia. Calcular os dígitos de uma recorrência em que cada valor depende do anterior não é, porque a ordem é obrigatória.

## As três medidas

Corre o mesmo programa em 1 núcleo e em $p$ núcleos e mede os tempos de parede (_wall-clock_), $T_1$ e $T_p$. A partir daí:

*   **Speedup**: $S_p = T_1 / T_p$. Quantas vezes mais rápido ficou.
*   **Eficiência**: $E_p = S_p / p$. Que fração do hardware foi aproveitada.
*   **Tempo de execução**: $T_p$ em segundos, a medida que o utilizador sente.

O speedup ideal com $p$ núcleos é $p$, com eficiência de 100 por cento. Na prática fica sempre abaixo, por três razões que vais reencontrar a cadeira toda. Há trabalho que não se divide (a fração serial), há custo de coordenação (criar threads, sincronizar, comunicar) e há recursos partilhados que saturam (a memória e a cache).

As três barras mostram onde vai o tempo no exemplo de baixo. A barra cheia são os 12 s sequenciais. A barra ideal comprime-os para 3 s. A barra real fica nos 4 s, e a fatia escura é exatamente o que a eficiência de 75 por cento perde, serial mais coordenação.

![Três barras de tempo. T1 com 12 segundos, Tp ideal com 3 segundos e Tp real com 4 segundos, com a última fatia marcada como serial mais coordenação.](https://resumos.rgo.pt/cadeiras/cpd/computacao-paralela-introducao/figura-1.svg)

## Exemplo completo

Um programa de tratamento de imagem demora $T_1 = 12$ s num núcleo e $T_4 = 4$ s em 4 núcleos. Calculamos:

$$
S_4 = \frac{12}{4} = 3{,}0 \qquad E_4 = \frac{3{,}0}{4} = 0{,}75
$$

O speedup é 3 e a eficiência é 75 por cento. A interpretação: dos 4 núcleos, um quarto do potencial perdeu-se. Os 12 s de trabalho sequencial viraram 4 s de relógio em vez dos 3 s ideais, por isso 1 s por núcleo foi para a fração serial e para o custo de coordenação. Se o enunciado pedir para julgar a paralelização, é isto que se responde, o número mais o destino do tempo perdido.

$S_4 = 12 / 4 = 3{,}0$ e $E_4 = 3{,}0 / 4 = 0{,}75$. Speedup 3, eficiência 75 por cento.

Um programa demora $T_1 = 20$ s e $T_8 = 4$ s. Então $S_8 = 20 / 4 = 5{,}0$ e $E_8 = 5{,}0 / 8 = 0{,}625$. Speedup 5, eficiência 62,5 por cento. Com o dobro dos núcleos, a eficiência caiu, porque a fatia de coordenação pesa mais no total.

Confere as contas correndo o cálculo:

```python
t1, tp, p = 12.0, 4.0, 4
s = t1 / tp
print("speedup:", s)
print("eficiência:", round(s / p, 2))
```

Como pensar em teste

Perante tempos com 1 e $p$ núcleos, calcula sempre as duas medidas e interpreta a eficiência. Uma eficiência abaixo de 50 por cento com poucos núcleos é sinal de que a coordenação ou a fração serial dominam, e sugere procurar o gargalo antes de pedir mais núcleos.

Speedup contra o quê

O speedup honesto compara contra o melhor programa sequencial conhecido[1](https://resumos.rgo.pt/cadeiras/cpd/computacao-paralela-introducao/#user-content-fn-speedup-honesto), não contra a versão paralela corrida com 1 thread. Comparar contra a versão paralela com uma thread esconde o custo da própria paralelização e inflaciona o número.

## Notas de rodapé

1.  A versão paralela com uma thread ainda paga o custo da paralelização, criar a equipa de threads e gerir acumuladores privados, por isso o seu tempo é maior que o do melhor sequencial. Usá-la como base divide por um número maior e o speedup sai artificialmente alto. [Voltar](https://resumos.rgo.pt/cadeiras/cpd/computacao-paralela-introducao/#user-content-fnref-speedup-honesto)