Computação Paralela¶
A aceleração paralela é limitada por dependências, coordenação, largura de banda da memória e pela fração sequencial de um programa.
Trabalho e caminho crítico¶
- Trabalho
T₁é o tempo em um processador. - Caminho crítico
T∞é a maior cadeia de dependências com processadores ilimitados. - O paralelismo é limitado por
T₁ / T∞.
Um algoritmo paralelo deve minimizar tanto o trabalho total quanto o caminho crítico. Um algoritmo com trabalho adicional pode ser pior mesmo que seu caminho crítico teórico seja menor.
Lei de Amdahl¶
Se a fração s for inerentemente sequencial e o restante escalar perfeitamente
em p processadores, a aceleração ideal será limitada por:
À medida que p cresce, a aceleração se aproxima de 1/s. O modelo é
simplificado, mas revela por que pequenos gargalos sequenciais importam.
Fork/Join¶
Divida o trabalho até que as tarefas sejam grandes o bastante para amortizar o custo de escalonamento; então calcule diretamente. Os limiares dependem da carga e do hardware e devem ser medidos. O roubo de trabalho ajuda a balancear tarefas irregulares, mas não corrige uma dependência fundamentalmente sequencial.
Hazards¶
- excesso de subscrição e criação excessiva de tarefas;
- contenção ou falso compartilhamento entre campos mutáveis próximos;
- saturação da largura de banda da memória;
- reduções não associativas que produzem arredondamentos diferentes;
- paralelismo aninhado usando os mesmos recursos limitados;
- bloqueio em um pool projetado para trabalho computacional.
Use medições representativas de ponta a ponta, não apenas microbenchmarks, quando o objetivo for o throughput ou a latência da aplicação.