Programação Paralela e por que você deveria se preocupar com isso (Parte 3)

Não é bem assim.

Nas publicações anteriores (veja as partes 1 e 2 desta série) foram discutidas diversas questões sobre o paradigma de Programação Paralela, tais como a importância de entender o paralelismo na construção de sistemas, os conceitos básicos, incluindo a taxonomia de Flynn, além de a iminência de sistemas cada vez mais concorrentes e paralelos.

Nesta parte, irei apresentar mais alguns conceitos de programação paralela, focando naqueles que definem o potencial de paralelismo de um sistema. Além disso, irei apresentar a lei de Amdahl, a qual é utilizada para calcular o ganho real na velocidade de processamento ao utilizar técnicas de paralelismo em um sistema.


Bom, já vimos que a programação paralela é necessária para implementar diversos tipos de sistemas complexos, e pode trazer diversos benefícios aos sistemas tradicionais, mas infelizmente ela não é viável para todo tipo de cenário. Desta forma, uma das maneiras de avaliar se é uma boa ideia utilizar programação paralela é identificando se um determinado tipo de problema é "Embaraçosamente Paralelo" (Embarrassingly Parallel), isto é, um problema que sua solução pode ser dividida em várias partes independentes, sem que seja necessária uma sincronização entre elas para chegar à solução final. Problemas, ou sistemas, embaraçosamente paralelos permitem que tarefas sejam executadas simultaneamente com pouca ou nenhuma necessidade de inter-coordenação.

Exemplificando o que foi escrito no parágrafo anterior, vamos analisar o caso de um sistema de edição gráfica que precisa realizar o processamento de uma imagem para deixá-la em escala de cinza. Este processamento pode ser dividido em várias partes? Não responda agora. Apenas pense no ambiente em que você irá realizar o processamento, um computador cujo processador possui 4 núcleos e permite a paralelização de tarefas (exatamente como a maioria dos computadores atuais). Agora veja a imagem a seguir:

Divisão do processamento em sub-tarefas, designadas para cada núcleo do processador multi-core.

Programas bem conhecidos como o Photoshop utilizam em sua codificação métodos que realizam a fragmentação de processos em sub-tarefas visando obter o máximo de paralelismo possível dos computadores. A imagem acima traduz essa divisão e responde à questão anterior sobre a possibilidade de dividir o processamento em várias partes.

Gene Amdahl.

Entretanto, já discutimos que a programação paralela não atende à todos os cenários. Foi pensando nisso que, em 1967, um arquiteto de computadores chamado Gene Amdahl (hoje esse senhor da foto ao lado) propôs na Spring Joint Computer Conference daquele ano uma lei que encontra o melhoramento máximo esperado para um sistema em geral quando somente parte do sistema é melhorada. Na computação paralela esta lei é utilizada para predizer o speedup teórico máximo alcançando quando um sistema utiliza múltiplos processadores em sua execução.

Muita calma nessa hora. Speedup? É, quase em tradução direta, o aumento da velocidade do programa.

Então, continuando, só o fato de utilizar programação paralela não irá fazer com que um sistema aumente sua performance indefinidamente. O speedup de um programa utilizando múltiplos processadores na computação paralela é limitado pelo tempo necessário para executar a fração sequencial do programa, ou seja, aquela parte do programa que não pode ser paralelizada.

Em outras palavras, na minha humilde tentativa de explicar mais didaticamente isso, tomemos como exemplo um programa que precisa de 20 horas para realizar uma tarefa utilizando um único núcleo do processador. Este programa possui uma porção particular que leva uma hora para ser executada e não pode ser paralelizada, enquanto as 19 horas restantes do tempo de execução do programa podem ser paralelizadas. Sendo assim, independente da quantidade de processadores que sejam utilizados para executar a parte paralelizável deste programa, o tempo de execução mínimo dele não poderá ser menor que uma hora. Desta forma, o speedup máximo alcançado ao utilizar paralelismo neste programa é limitado a um valor 20x maior que o atual.

A lei de Amdahl é definida através da seguinte fórmula:

Fórmula de Amdahl.

Onde P = fração de código paralelizável. Ou seja a porcentagem do programa que pode utilizar múltiplos processadores.

• Se nenhum código puder ser paralelizado, P = 0, então o speedup é igual a 1 (não há melhoramento).
• Se todo o código puder ser paralelizado, P = 1, então o speedup tende ao infinito (na teoria).
• Se 50% do código puder ser paralelizado, P = 0.5, então o speedup máximo é 2, o que significa que o programa irá executar duas vezes mais rápido.

Introduzindo na fórmula o número de processadores que irão realizar a fração paralela do programa, o relacionamento pode ser modelado assim:

Fórmula de Amdahl envolvendo a quantidade de processadores.

Onde P = fração paralelizável, N = número dos processadores e S = fração sequencial.
Nesta segunda fórmula, torna-se claro que existem limites para a escalabilidade do paralelismo nas aplicações. Realizei os cálculos abaixo variando a porção paralelizável dos programas, aumentando a quantidade de processadores. Observe no gráfico que o speedup obtido chega em um limite, independente de quantos processadores sejam utilizados.

Com tudo que foi discutido até aqui fica claro que uma análise detalhada de cada aplicação é necessária antes de partir para a programação paralela. Muitas vezes o "custo-benefício" para aplicar paralelismo em um programa não vale a pena, já que algoritmos paralelos são mais difíceis de escrever e manter. A não ser que o speedup obtido seja realmente relevante. E com isso, a terceira parte dessa série se encerra. Espero que tenha sido útil. Até a próxima.