Pular para o conteúdo principal

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.


Comentários


  1. My programmer is trying to persuade me to move to .net from PHP. I have always disliked the idea because of the expenses. But he's tryiong none the less. I've been using Movable-type on numerous websites for about a year and am worried about switching to another platform. I have heard fantastic things about blogengine.net. Is there a way I can import all my wordpress posts into it? Any help would be greatly appreciated! yahoo login

    ResponderExcluir

Postar um comentário

Postagens mais visitadas deste blog

Utilizando o padrão de referências da ABNT no Word

Uma importante funcionalidade do Microsoft Word é o seu Gerenciador de Fontes Bibliográficas. Para aqueles que estão escrevendo algum trabalho acadêmico ou científico, é possível cadastrar todas as referências do trabalho e no final gerar a listagem já enumerada dos documentos que foram consultados na pesquisa. Essa postagem traz os arquivos necessários e as instruções para facilitar essa etapa da elaboração.

Como resetar completamente uma instalação do Apache no Ubuntu

Quando eu estava experimentando o módulo python do Apache (mod_python), eu 'de alguma maneira' estraguei minha instalação do Apache. Os arquivos de configuração ficaram em um estado estranho, então eu excluí a pasta /etc/apache2, removi o Apache (através do dpkg) e o reinstalei. Mas o resultado não foi como esperado, a pasta /etc/apache2 não foi recriada na instalação.

Como interpretar e utilizar gráficos

A quantidade de uma única postagem nos últimos 5 anos de blog mostra o quanto estive focado em outras coisas e sem tempo para escrever aqui. Porém, no meio de uma pandemia e com a finalização do meu doutorado, acabei ficando com mais tempo e colocando como meta a volta das publicações aqui no blog.
Nunca antes na história desse país a população, de uma maneira geral, se preocupou tanto com gráficos, curvas, média e outras questões básicas da estatística. Assim, em tempos de coronavírus, essa postagem tem o objetivo de auxiliar que mais e mais pessoas consigam interpretar gráficos, fazer comparações e, inclusive, saber o melhor tipo de gráfico para usar em determinados casos.